Carrot_killer @ 2018-01-16 19:48:22
求大神指点指点
上代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,ff=1;
int use[100001][3];
int dp[100001];
struct node{
int a,t,g,imp;
}p[1000001];
node an[1000001];
void create(int k){
node q[5];
q[1]=p[k];
node f;
f.a=p[k].a+p[use[k][1]].a;
f.g=0;
f.t=p[k].t+p[use[k][1]].t;
f.imp=p[k].a*p[k].t+p[use[k][1]].a*p[use[k][1]].t;
q[2]=f;
f.a=p[k].a+p[use[k][2]].a;
f.g=0;
f.t=p[k].t+p[use[k][2]].t;
f.imp=p[k].a*p[k].t+p[use[k][2]].a*p[use[k][2]].t;
q[3]=f;
f.a=p[k].a+p[use[k][1]].a+p[use[k][2]].a;
f.g=0;
f.t=p[k].t+p[use[k][1]].t+p[use[k][2]].t;
f.imp=p[k].a*p[k].t+p[use[k][1]].a*p[use[k][1]].t+p[use[k][2]].a*p[use[k][2]].t;
q[4]=f;
int oh=1;
while(oh<5){
an[ff]=q[oh];
oh++;
ff++;
}
}
void fill(int h){
int temp=1;
while(use[p[h].g][temp]!=0) temp++;
use[p[h].g][temp]=h;
use[h][0]=-1;//this one have removed!
}
int main(){
memset(use,0,sizeof(use));
cin>>m>>n;
for(int i=1;i<=n;i++){
use[i][0]=i;
cin>>p[i].a>>p[i].t>>p[i].g;
p[i].imp=p[i].t*p[i].a;
if(p[i].g!=0){
fill(i);
}
}
for(int i=1;i<=n;i++){
if(use[i][0]!=-1){
if(use[i][1]==0){
an[ff]=p[i];
ff++;
}
else create(i);
}
}
for(int i=1;i<=ff;i++){
for(int j=m;j>=an[i].a;j--){
dp[j]=max(dp[j],dp[j-an[i].a]+an[i].imp);
}
}
cout<<dp[m];
return 0;
}