#include <iostream>
#include <algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
using namespace std;
int s[200000]={0},t[20000]={0};
int n,m,i,j,k,w[200000],v[200000],p[200000];
int main()
{
cin>>n>>m;
for (i=1;i<=m;i++)
{
cin>>w[i]>>v[i]>>p[i];
v[i]*=w[i];//重要度和价格的乘积
}
for (i=1;i<=m;i++)
{
s[0]=0;
if (p[i]==0) //如果是主件
{
for (j=w[i];j<=n;j++)//t【j】存这组物品选择后可以得到的最大值
t[j]=s[j-w[i]]+v[i];//选主件
for (j=1;j<=m;j++)
if (p[j]==i)//如果是i的附件
{
for (k=n;k>=w[j]+w[i];k--)//在选了主件的基础上再01
t[k]=max(t[k],t[k-w[j]]+v[j]);//判断选不选
}
}
for (j=w[i];j<=n;j++)
{
if (t[j]>s[j])
s[j]=t[j];
}
}
printf("%d",s[n]);
return 0;
}
1 条评论
-
xyt520 LV 9 @ 2017-09-14 16:54:24
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
long long ll;
const int N=30+3200;
using namespace std;
typedef struct
{
int v,p,q,c;
}G;G g[66];
int dp[N];
int main()
{
int i,j,a,b;
int m,n,x,y;
memset(g,0,sizeof(g));
scanf("%d%d",&m,&n);
for(i=1;i<=n;i++) cin>>g[i].v>>g[i].p>>g[i].q,g[i].v/=10,g[i].c=g[i].p*g[i].v;
m/=10;
for(i=1;i<=n;i++)
if(g[i].q==0)
{
for(j=2;j<=n;j++) if(g[j].q==i) break; a=g[j].c;int a1=g[j].v;
for(j++;j<=n;j++) if(g[j].q==i) break; b=g[j].c;int b1=g[j].v;
for(j=m;j>=g[i].v;j--)
{
dp[j]=max(dp[j],dp[ j-g[i].v ]+g[i].c);
x=g[i].v+a1; y=g[i].c+a;
if(x<=j) dp[j]=max(dp[j],dp[j-x]+y);
x=g[i].v+b1; y=g[i].c+b;
if(x<=j) dp[j]=max(dp[j],dp[j-x]+y);
x=g[i].v+a1+b1; y=g[i].c+a+b;
if(x<=j) dp[j]=max(dp[j],dp[j-x]+y);
}
}
cout<<dp[m]*10<<endl;
return 0;
}
你自己看吧
- 1
