[C++] 純文本查看 復制代碼
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<iostream>
using namespace std;
struct item{
int v;
int p;
int w;
};
item obj[61];
vector<item> part[61];
int dp[61][3200][2];
int main()
{
int V,N,pn,pl;
while(~scanf("%d%d",&V,&N))
{
V/=10;
for(int i=1;i<=N;++i)
part.clear();
for(int i=1;i<=N;++i)
{
scanf("%d%d%d",&obj.v,&obj.p,&obj.w);
obj.v/=10;
if(obj.w)
part[obj.w].push_back(obj);
}
memset(dp,0,sizeof(dp));
pn=pl=0;
for(int i=1;i<=N;++i)
{
if(obj.w)
continue;
pl=pn;
pn=i;
for(int j=0;j<=V;++j)
{
dp[pn][j][0]=max(dp[pl][j][0],dp[pl][j][1]);
if( j-obj.v < 0 )
dp[pn][j][1]=0;
else
dp[pn][j][1]=obj.v*obj.p+max(dp[pl][j-obj.v][0],dp[pl][j-obj.v][1]);
}
for(int k=0 ; k<part.size() ; ++k)
{
item &t=part[k];
for( int j=V; j>=t.v ;--j )
{
if( dp[pn][j-t.v][1] && dp[pn][j][1] )
dp[pn][j][1] = max( dp[pn][j][1] , dp[pn][j-t.v][1]+t.v*t.p );
}
}
}
int ans=0;
for(int i=0;i<=V;++i)
{
ans =max(ans ,dp[pn][0] );
ans =max(ans ,dp[pn][1] );
}
printf("%d\n",ans*10);
}
}