40pts 悬关求调

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

Wildchesse @ 2023-06-01 19:58:30

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define MAXM 65
#define MAXN 32005
using namespace std;
int n,m,v[MAXM],p[MAXM],q[MAXM],f[MAXN],nx[MAXN][5],ans=-1e9,pans=-1e9;
signed main(){
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>v[i]>>p[i]>>q[i];
        if(q[i]!=0 and !nx[q[i]][1]){
            nx[q[i]][1]=i;
        }
        else if(q[i]!=0 and !nx[q[i]][2]){
            nx[q[i]][2]=i;
        }
    }
    for(int i=1;i<=m;i++){
        if(q[i]){
            continue;
        }
        for(int j=n;j>=v[i];j--){
            pans=max(f[j],f[j-v[i]]+v[i]*p[i]);
            if(nx[i][1]!=0  and j>=v[i]+v[nx[i][1]]){
                pans=max(pans,f[j- v[i] - v[nx[i][1]]]
                + v[i]*p[i] + v[nx[i][1]]*p[nx[i][1]] );
            }
            if(nx[i][2]!=0  and j>=v[i]+v[nx[i][2]]){
                pans=max(pans,f[j-v[i] - v[nx[i][2]]]
                + v[i]*p[i] + v[nx[i][2]]*p[nx[i][2]]);
            }
            if(nx[i][2]!=0  and j>=v[i]+v[nx[i][1]]+v[nx[i][2]]){
                pans=max(pans,f[j-v[i] - v[nx[i][1]] - v[nx[i][2]]]
                + v[i]*p[i] + v[nx[i][1]]*p[nx[i][1]] +v[nx[i][2]]*p[nx[i][21]]);
            }
            f[j]=pans;
        }
    }
    cout<<f[n];
    return 0;
}

对照题解,认为错误出在存储方式上但找不出来为什么会错,恳请各位大佬能不能帮帮这位蒟蒻捏QWQ


by Wildchesse @ 2023-06-01 20:01:51

或者给一组m<6的hack也行


by ninji @ 2023-06-05 21:36:39

@Wildchesse

hack
2000 5
100 3 0
1000 3 1
400 5 0
300 5 0
1400 2 3

by ninji @ 2023-06-05 21:37:03

@Wildchesse 此题有坑!!!


by ninji @ 2023-06-05 21:39:02

hack
2000 5
100 3 0
1000 3 1
400 5 0
300 5 0
1400 2 3
ans:6800

|