关于列举的顺序问题

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

Quasimodo @ 2017-10-04 23:56:28

代码是参照题解区一位大佬思路写出来的,在循环枚举物品的时候,第一次是顺序(1~n),wa了第六个点,xjb改成了(n~1)就ac掉了,请教一下为什么啊

####include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int dp[35000];
int n,m;
int ac[35000],aw[35000],bc[35000][5],bw[35000][5];
int v,p,q;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
       cin>>v>>p>>q;
       if(!q)
       {
           ac[i]=v;
           aw[i]=v*p;
       }
       else
       {
           bc[q][0]++;
           bc[q][bc[q][0]]=v;
           bw[q][bc[q][0]]=v*p;
       }
    }
    memset(dp,0,sizeof(dp));
    for(int i=m;i>=1;i--)//这个位置
    for(int j=n;j>0;j--)
    {
        dp[j]=max(dp[j],dp[j-ac[i]]+aw[i]);
        if(j-ac[i]<bc[i][1]&&j-ac[i]<bc[i][2])
        break;
        else
        {    
        if(j>=ac[i]+bc[i][1])
         dp[j]=max(dp[j],dp[j-ac[i]-bc[i][1]]+aw[i]+bw[i][1]);
         if(j>=ac[i]+bc[i][2])
         dp[j]=max(dp[j],dp[j-ac[i]-bc[i][2]]+aw[i]+bw[i][2]);
         if(j>=ac[i]+bc[i][1]+bc[i][2])
         dp[j]=max(dp[j],dp[j-ac[i]-bc[i][1]-bc[i][2]]+aw[i]+bw[i][1]+bw[i][2]);
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}

|