蒟蒻求助,测试点8WA

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

JiJiZi @ 2023-02-14 16:02:21

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3.2* 10000 + 5,MAXM = 65;
int n,m;
int f[MAXN];
int cnt[MAXM],w[MAXM],v[MAXM];
int t[MAXM][MAXM];
int al[MAXM];
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++){
        int k;
        scanf("%d%d%d",&w[i],&v[i],&k);
        if(k!=0) al[i]++,cnt[k]++;t[k][cnt[k]] = i;
    }
    for(int i = 1;i <= m;i++){
    if(al[i] != 0) continue;
    for(int j = n;j >= w[i];j--){
        f[j] = max(f[j],f[j-w[i]]+w[i]*v[i]);
        if((w[i] + w[t[i][1]]) <= j) f[j] = max(f[j],f[j-w[i]-w[t[i][1]]] +w[t[i][1]]*v[t[i][1]]+w[i]*v[i]);
        if((w[i] + w[t[i][2]]) <= j) f[j] = max(f[j],f[j-w[i]-w[t[i][2]]] +w[t[i][2]]*v[t[i][1]]+w[i]*v[i]);
        if((w[i] + w[t[i][1]] + w[t[i][2]]) <= j) f[j] = max(f[j],f[j-w[i]-w[t[i][1]] - w[t[i][2]]] +w[t[i][2]]*v[t[i][2]] +w[t[i][1]]*v[t[i][1]]+w[i]*v[i]);
    }
    }
    printf("%d",f[n]);
    return 0;
}

不知道为什么测试点8不能通过,有好心人分享下测试点8的数据嘛。


by JiJiZi @ 2023-02-14 16:06:10

把附件和主体讨论的时候写的有点乱。其他测试点都能过,今天一次下载机会已经没有了,呜呜呜~


|