赤霞QvQ @ 2019-06-23 15:04:32
程序:
#include<bits/stdc++.h>
using namespace std;
int n,m,v,p,q,zhuv[65],zhuw[65],fuv[65][3],fuw[65][3],dp[32005];
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>v>>p>>q;
if(q==0)
{
zhuv[i]=v;
zhuw[i]=v*p;
}
else
{
fuv[i][0]++;
fuv[i][fuv[i][0]]=v;
fuw[i][fuv[i][0]]=v*p;
}
}
for(int i=1;i<=m;i++)
{
if(zhuv[i]!=0)
{
for(int j=n;j>=zhuv[i];j--)
{
dp[j]=max(dp[j],dp[j-zhuv[i]]+zhuw[i]);
if(j>=zhuv[i]+fuv[i][1])
{
dp[j]=max(dp[j],dp[j-zhuv[i]-fuv[i][1]]+zhuw[i]+fuw[i][1]);
}
if(j>=zhuv[i]+fuv[i][2])
{
dp[j]=max(dp[j],dp[j-zhuv[i]-fuv[i][2]]+zhuw[i]+fuw[i][2]);
}
if(j>=zhuv[i]+fuv[i][1]+fuv[i][2])
{
dp[j]=max(dp[j],dp[j-zhuv[i]-fuv[i][1]-fuv[i][2]]+zhuw[i]+fuw[i][1]+fuw[i][2]);
}
}
}
}
cout<<dp[n]<<endl;
return 0;
}
真心查不出错哪了?
by 时间圣使·凡 @ 2019-06-23 16:08:46
by WatchmanIce @ 2019-06-23 19:45:26
@无赖学哥 蒟蒻来看看
by WatchmanIce @ 2019-06-23 19:47:15
@无赖学哥 这题树形dp啊蒟蒻开始瞎bb
by 赤霞QvQ @ 2019-06-23 21:37:40
@最帅的帅哥 P1064
by 赤霞QvQ @ 2019-06-23 21:37:52
@David崔 ????
by WatchmanIce @ 2019-06-25 19:54:35
@无赖学哥 应该是树形dp
by WatchmanIce @ 2019-06-25 19:54:55
@David崔 他们的关系网构成了一棵树