Yorue夜绘 @ 2018-11-25 18:20:00
P1064 金明的预算方案
请问,为什么我没有加
for(int i=1;i<=n;i++)
ans=max(ans,f[m][i]);
请问,为什么我没有加,还是AC了?
#include<iostream>
#include<algorithm>
using namespace std;
int c[70][3],w[70][3],f[70][32010],ans;
int main(void)
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
if(z==0) c[i][0]=x,w[i][0]=x*y;
else
{
if(c[z][1]==0) c[z][1]=x,w[z][1]=x*y;
else c[z][2]=x,w[z][2]=x*y;
}
}
for(int k=1;k<=m;k++)
for(int t=1;t<=n;t++)
{
f[k][t]=f[k-1][t];
if(t-c[k][0]>=0)
f[k][t]=max(f[k][t],f[k-1][t-c[k][0]]+w[k][0]);
if(t-c[k][0]-c[k][1]>=0)
f[k][t]=max(f[k][t],f[k-1][t-c[k][0]-c[k][1]]+w[k][0]+w[k][1]);
if(t-c[k][0]-c[k][2]>=0)
f[k][t]=max(f[k][t],f[k-1][t-c[k][0]-c[k][2]]+w[k][0]+w[k][2]);
if(t-c[k][0]-c[k][1]-c[k][2]>=0)
f[k][t]=max(f[k][t],f[k-1][t-c[k][0]-c[k][1]-c[k][2]]+w[k][0]+w[k][1]+w[k][2]);
}
cout<<f[m][n]<<endl;
return 0;
}
by Adove @ 2018-11-25 18:28:29
因为f[m][n]
本来就是最后的答案吧QAQ,还有为什么要在这里发AC代码啊
by Yorue夜绘 @ 2018-11-25 18:36:09
f[m][n]不是考虑前m个物品,时间恰为n的最大价值吗?所以应该对所有的n取最大才是答案呀,但是为什么我AC了
by 替罪羊树 @ 2018-11-25 18:59:58
@tkotw 建议打个表观察一下,你会发现整个表从左上到右下是递增的
by Yorue夜绘 @ 2018-11-25 19:02:35
@替罪羊树 谢谢
by realskc @ 2018-11-25 19:04:28
@skip2004 巨佬