求助 !!

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

j_steady @ 2022-08-06 13:27:50

#include <bits/stdc++.h>
#define vi val[i]
#define wi w[i]
#define vim1 val[maj_2[i][1]]
#define wim1 w[maj_2[i][1]]
#define vim2 val[maj_2[i][2]]
#define wim2 w[maj_2[i][2]]
using namespace std;
int n,m,val[65],ans = 0,major[65],w[65],maj_2[65][65],cnt[65],f[320005];
int main (){
    scanf ("%d%d",&m,&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&val[i],&w[i],&major[i]);
        maj_2[major[i]][++cnt[major[i]]] = i;
    }
    /*puts("qwq");
    for(int i = 1;i<=n;i++){
        printf ("%d qwqwwqwqw\n",major[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j =1;j<=2;j++){
            printf ("%d ",maj_2[i][j]);
        }
        puts("");
    }*/
    for(int i=1;i<=n;i++){
        for(int j = m;j>=0;j --){
            if(!major[i]){ 
                if(j >= vi) f[j] = max(f[j],f[j-vi]+vi * wi);
                if(maj_2[i][1] && j>=vi+vim1) f[j] = max(f[j],f[j-vim1-vi]+vim1*wim1+vi*wi); 
                if(maj_2[i][2] && j>=vi+vim2)  f[j] = max(f[j],f[j-vim2-vi]+vim2*wim2+vi*wi);
                if(maj_2[i][1] && maj_2[i][2] && j>=vi+vim1+vim2) f[j] = max(f[j],f[j-vim1-vim2-vi] + vi*wi+vim2*wim2+vim1*wim1);   
            }
        }
    } 
    for(int i=1;i<=m;i++){
        ans = max(ans,f[i]);
    }
    printf ("%d",ans);
    return 0;
} 

为什么 maj_2 数组 第二位要开到65 开小了就炸了 但cnt数组不应该只能到2嘛 qwq

谢谢 orz


by interestingLSY @ 2022-08-06 18:28:41

cnt[0] 不一定小于等于二


by metaphysis @ 2022-08-08 16:35:39

@j_steady

楼上已指出原因。


by j_steady @ 2022-08-08 17:03:12

谢谢大家


|