求调!

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

MWL_wma @ 2023-12-24 16:21:53

不知道哪里错了,玄关,谢谢

#include<bits/stdc++.h>
using namespace std;
int n,m;
int s[62][4],v[62][4],f[32000];
int main(){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(!c){
            s[i][1]=a,v[i][1]=a*b;
            s[i][0]=1,v[i][0]=1;
        }else{
            s[c][0]++,
            s[c][s[c][0]]=s[c][1]+a;
            v[c][0]++,
            v[c][v[c][0]]=v[c][1]+a*b;
            --n,--i;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=s[i][1];j--){
            int mx=f[j-s[i][1]]+v[i][1];
            if(j>=s[i][1]+s[i][2])
                mx=max(mx,f[j-s[i][1]-s[i][2]]+v[i][1]+v[i][2]);
            if(j>=s[i][1]+s[i][3])
                mx=max(mx,f[j-s[i][1]-s[i][3]]+v[i][1]+v[i][3]);
            if(j>=s[i][1]+s[i][2]+s[i][3])
                mx=max(mx,f[j-s[i][1]-s[i][2]-s[i][3]]+v[i][1]+v[i][2]+v[i][3]);
            f[j]=mx;
        }
        //printf("%d\n",f[m]);
    }
    printf("%d",f[m]);
    return 0;
}

by MWL_wma @ 2023-12-24 16:22:27

AC 1#,其他 WA


by TangyixiaoQAQ @ 2023-12-24 22:10:31

@yma_y_wma

首先

int mx=f[j-s[i][1]]+v[i][1];

这样判断上一步的最优解又去哪里了呢?

其次

顺序结构特有的可爱(ex)数据结构,导致你这里用mx就无法更新。

所以建议转移的时候直接用f[j]

最后

这个输入建议改一改

for(int i=1;i<=n;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(!c){
            s[i][1]=a,v[i][1]=a*b;
            s[i][0]=1,v[i][0]=1;
        }else{
            s[c][0]++,
            s[c][s[c][0]]=s[c][1]+a;
            v[c][0]++,
            v[c][v[c][0]]=v[c][1]+a*b;
            --n,--i;
        }
    }

尤其是

--n,--i;

by MWL_wma @ 2023-12-24 22:39:05

@TangyixiaoQAQ 感觉你很强,说得 very 有理,但是好像过不了(40 tps)


by TangyixiaoQAQ @ 2023-12-25 16:04:04

@yma_y_wma 输入改了吗


|