7.3训练日记

今天风好大,刮台风了吧 P1064 [NOIP2006 提高组] 金明的预算方案 带有约束的背包类型,约束数目一开始没有看到,导致想不到这个题 这个题目每个物品最多有两个附件,那么可以考虑对主件单独决策. 对于每个主件和他们的附件,有以下考虑. 1.选择主件和对应的两个附件 2.选择主件和对应一个附件(附件1/2) 3.选择主件 4.不选该主件

#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define int long long
#define all(a) (a).begin(), (a).end()
signed main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m;cin>>m>>n;
	vector v(n+1,0),p(n+1,0),q(n+1,0);
	for(int i=1;i>v[i]>>p[i]>>q[i];
	}
	vector sub(n+1);
	for(int i=1;i=v[i]) dp[j] = max(dp[j],dp[j-v[i]]+v[i]*p[i]);
			//select 2 object 
			vector tmp;
			for(int k=0;k=v[i]+v[t]) dp[j] = max(dp[j],dp[j-v[i]-v[t]]+v[i]*p[i]+v[t]*p[t]);
			}
			//select 3 object
			if(tmp.size()>=2&&(j>=v[i]+v[tmp[0]]+v[tmp[1]])){
				dp[j] = max(dp[j],dp[j-v[i]-v[tmp[0]]-v[tmp[1]]]+v[i]*p[i]+v[tmp[0]]*p[tmp[0]]+v[tmp[1]]*p[tmp[1]]);
			}
		}
	}
	cout