40分WA,大佬帮帮忙(代码思路奇怪)

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

LS时空光影 @ 2022-07-10 21:19:56

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int n,m,i,j,k,l,x,y,z,f[40000];
vector<int> a[100][3];
int main(){
    scanf("%d%d",&m,&n);
    for(i=1;i<=n;i++){
        scanf("%d%d%d",&x,&y,&z);
        if(z==0) a[i][0].push_back(x),a[i][1].push_back(y);
        else a[z][0].push_back(x),a[z][1].push_back(y);
    }
    for(i=1;i<=n;i++)
        if(a[i][0].size()!=0)
            for(j=m;j>=a[i][0][0];j--)
                if(f[j-1]<f[j-a[i][0][0]]+a[i][0][0]*a[i][1][0]){
                    f[j]=f[j-a[i][0][0]]+a[i][0][0]*a[i][1][0];
                    for(k=1;k<a[i][0].size();k++)
                        if(j+a[i][0][k]<=m)
                            f[j+a[i][0][k]]=max(f[j+a[i][0][k]-1],f[j]+a[i][0][k]*a[i][1][k]);
                }
    printf("%d\n",f[m]);
    return 0;
}

|