依赖背包-金明的预算方案
陈子骏
2018-04-01 16:55:26
```
#include<bits/stdc++.h>
using namespace std;
int n,m,f[70][35000],cnt;
struct ii{
int w,num,va;
}w[100][5];
void cz(int i){
for(int j=n;j>=0;j--){
if(j-w[i][0].w>=0) {
f[i][j]=max(f[i-1][j-w[i][0].w]+w[i][0].w*w[i][0].num,f[i-1][j]);
if(j-w[i][0].w-w[i][1].w>=0)
f[i][j]=max(f[i-1][j-w[i][0].w-w[i][1].w]+w[i][0].w*w[i][0].num+w[i][1].w*w[i][1].num,f[i-1][j]);
else if(j-w[i][0].w-w[i][2].w>=0)
f[i][j]=max(f[i-1][j-w[i][0].w-w[i][2].w]+w[i][0].w*w[i][0].num+w[i][2].w*w[i][2].num,f[i-1][j]);
if(j-w[i][0].w-w[i][2].w>=0)
f[i][j]=max(f[i-1][j-w[i][0].w-w[i][2].w]+w[i][0].w*w[i][0].num+w[i][2].w*w[i][2].num,f[i-1][j]);
else if(j-w[i][0].w-w[i][1].w>=0)
f[i][j]=max(f[i-1][j-w[i][0].w-w[i][1].w]+w[i][0].w*w[i][0].num+w[i][1].w*w[i][1].num,f[i-1][j]);
if(j-w[i][0].w-w[i][1].w-w[i][2].w>=0)
f[i][j]=max(f[i-1][j-w[i][0].w-w[i][1].w-w[i][2].w]+w[i][0].w*w[i][0].num+w[i][1].w*w[i][1].num+w[i][2].w*w[i][2].num,f[i-1][j]);
}
else f[i][j]=f[i-1][j];
}
}
int main(){
scanf("%d%d",&n,&m);
n=n/10 ;
for(int i=1;i<=m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(!c){
cnt++;
w[cnt][0].w=a/10;
w[cnt][0].num=b;
w[cnt][0].va=a*b/10;
}
else{
if(!w[c][1].w) {
w[c][1].w=a/10;
w[c][1].num=b;
w[c][1].va=a*b/10;
}
else{
w[c][2].w=a/10;
w[c][2].num=b;
w[c][2].va=a*b/10;
}
}
}
for(int i=1;i<=cnt;i++){
cz(i);
}
printf("%d",f[cnt][n]*10);
}
```