P1064 [NOIP 2006 提高组] 金明的预算方案

点击查看代码

#include<bits/stdc++.h>
using namespace std;const int N=65,M=4e4;
int f[M];
int mw[N],mv[N];
int fw[N][3],fv[N][3];
int n,m;int main()
{ios::sync_with_stdio(0),cin.tie(0);cin>>n>>m;for(int i=1;i<=m;i++){int v,p,q;cin>>v>>p>>q;int val=v*p;if(q==0){mw[i]=v,mv[i]=val;}else if(!fw[q][1]){fw[q][1]=v,fv[q][1]=val;}else if(!fw[q][2]){fw[q][2]=v,fv[q][2]=val;}}for(int i=1;i<=m;i++){if(!mv[i]) continue;int w0=mw[i],v0=mv[i];int w1=fw[i][1],v1=fv[i][1];int w2=fw[i][2],v2=fv[i][2];for(int j=n;j>=w0;j--){f[j]=max(f[j],f[j-w0]+v0);if(w1&&j>=w0+w1){f[j]=max(f[j],f[j-w0-w1]+v0+v1);}if(w2&&j>=w0+w2){f[j]=max(f[j],f[j-w0-w2]+v0+v2);}if(w1&&w2&&j>=w0+w1+w2){f[j]=max(f[j],f[j-w0-w1-w2]+v0+v1+v2);}}}cout<<f[n]<<endl;return 0;
}