[已AC] “我之前是怎么错的?”

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

l55584 @ 2021-07-29 18:35:43

原先的代码:

#include <bits/stdc++.h>
using namespace std;
int n,m;int v[61],p[61],q[61];vector<int> tag[61];
int f[32001];
inline int rul(int a)
{
    return v[a]*p[a];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>v[i]>>p[i]>>q[i];
        if(q[i]!=0) tag[q[i]].push_back(i);
     } 
    for(int i=1;i<=m;i++)if(q[i]==0)
    for(int j=n;j>=v[i];j--)
    {
        if(f[j]<=f[j-v[i]]+rul(i))
        {
            f[j]=f[j-v[i]]+rul(i);
            if(tag[i].size()>=1&&j>=(v[i]+v[tag[i][0]])) f[j]=max(f[j],f[j-v[i]-v[tag[i][0]]]+rul(tag[i][0])+rul(i));
            if(tag[i].size()>=2&&j>=(v[i]+v[tag[i][1]])) f[j]=max(f[j],f[j-v[i]-v[tag[i][1]]]+rul(tag[i][1])+rul(i));
            if(tag[i].size()>=2&&j>=(v[i]+v[tag[i][1]]+v[tag[i][0]])) f[j]=max(f[j],f[j-v[i]-v[tag[i][1]]-v[tag[i][0]]]+rul(tag[i][1])+rul(i)+rul(tag[i][0]));
        }
    }
    cout<<f[n];
    return 0;
}

WA掉了#5#7

之后我把20~22行改为:(第一个判断和容量的范围)

    for(int j=n;j>=0;j--)
    {
        if(j>=v[i]) f[j]=max(f[j],f[j-v[i]]+rul(i));

就过了????

蒟蒻觉得两者没有本质区别。。望dalao指出


by BotDand @ 2021-07-29 18:40:18

数组越界


|