衣香鬓影 @ 2018-09-29 09:50:33
我的想法是直接把附件挂在主件下面,用了vecto<int> a[61],然后根据每个a[i]数组大小判断有几个附件. 代码如下:
#include<iostream>
#include<vector>
using namespace std;
struct wupin
{
int v;
int p;
int q;
};
vector<wupin> a[61];
long long dp[32005];
int max(int x,int y)
{
return x>y?x:y;
}
int main()
{
int money;
int n;
int zhu=0;
cin>>money>>n;
for(int i=1;i<=n;i++)
{
wupin x;
cin>>x.v>>x.p>>x.q;
if(x.q>0) a[x.q].push_back(x);
if(x.q==0)
{
zhu++;
if(!a[zhu].empty())
{
a[zhu].push_back(a[zhu][0]);
a[zhu][0]=x;
}
else a[zhu].push_back(x);
}
}
for(int i=1;i<=zhu;i++)
{
wupin now=a[i][0];
for(int j=money;j>=now.v;j--)
{
dp[j]=max(dp[j],dp[j-now.v]+now.v*now.p);
if(a[i].size()>=2)
if(j>=now.v+a[i][1].v)
dp[j]=max(dp[j],dp[j-now.v-a[i][1].v]+now.v*now.p+a[i][1].v*a[i][1].p);
if(a[i].size()>=3)
{
if(j>=now.v+a[i][2].v)
dp[j]=max(dp[j],dp[j-now.v-a[i][2].v]+now.v*now.p+a[i][2].v*a[i][2].p);
if(j>=now.v+a[i][1].v+a[i][2].v)
dp[j]=max(dp[j],dp[j-now.v-a[i][1].v-a[i][2].v]+now.v*now.p+a[i][1].v*a[i][1].p+a[i][2].v*a[i][2].p);
}
}
}
cout<<dp[money]<<endl;
}
第三个点总是过不了:
2000 10
500 1 0
400 4 0
300 5 1
400 5 1
200 5 0
500 4 5
400 4 0
320 2 0
410 3 0
400 3 5
题解答案:7430
我的答案:7200
想破脑袋也没想出来哪里有错。。。 请各位帮帮忙,谢谢大家了