请问,为什么我AC了?

P1064 [NOIP2006 提高组] 金明的预算方案

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 巨佬


|