萌新求助

zjrdmd @ 2020-06-07 10:25:07

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stdlib.h>
#include <stack>
#include <queue>
#define ri register int
#define N 100
#define M 1000005

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}

int son[N][5],w[N],v[N];
int cnt[N],fat[N];
int dp[M];

int main(){
    int m=read(),n=read();
    for(ri i=1;i<=n;i++){
        int a=read(),b=read(),fa=read();
        son[fa][++cnt[fa]]=i;
        if(fa)fat[i]++;
        w[i]=a*b,v[i]=a;
    } 
    for(ri i=1;i<=n;i++){
        if(!fat[i]){
            for(ri j=m;j>=v[i];j--){
                dp[j]=std::max(dp[j],dp[j-v[i]]+w[i]);
                if(j-(v[i]+v[son[i][1]])>=0)
                    dp[j]=std::max(dp[j],dp[j-v[i]-v[son[i][1]]]+w[i]+w[son[i][1]]);
                if(j-(v[i]+v[son[i][2]])>=0)
                    dp[j]=std::max(dp[j],dp[j-v[i]-v[son[i][2]]]+w[i]+w[son[i][2]]);
                if(j-(v[i]+v[son[i][2]]+v[son[i][1]])>=0)
                    dp[j]=std::max(dp[j],dp[j-v[i]-v[son[i][1]]-v[son[i][2]]]+w[i]+w[son[i][1]]+w[son[i][2]]);
            }
        }
    }
    printf("%d",dp[m]);
    return 0;
}

by dо_while_true @ 2020-06-07 10:33:16

什么问题，是RE吗

by dо_while_true @ 2020-06-07 10:33:55

@zjrqwq 如果主件的个数大于等于5的话显然son会越界吧

by zjrdmd @ 2020-06-07 10:38:50

@dо_while_true WA，并且题目里不是说了一个主件最多有2个附件吗/kk

by dо_while_true @ 2020-06-07 10:43:03

@zjrqwq 如果为主件，那么fa=0，则你的主件的信息都会存在son[0]里面，会越界

by dо_while_true @ 2020-06-07 10:50:44

@zjrqwq

改成这样就AC了，是数组越界的问题

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stdlib.h>
#include <stack>
#include <queue>
#define ri register int
#define N 100
#define M 1000005

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}

int son[N][5],w[N],v[N];
int cnt[N],fat[N];
int dp[M];

int main(){
    int m=read(),n=read();
    for(ri i=1;i<=n;i++){
        int a=read(),b=read(),fa=read();
        if(fa) {
            son[fa][++cnt[fa]]=i;
            fat[i]++;   
        }
        w[i]=a*b,v[i]=a;
    } 
    for(ri i=1;i<=n;i++){
        if(!fat[i]){
            for(ri j=m;j>=v[i];j--){
                dp[j]=std::max(dp[j],dp[j-v[i]]+w[i]);
                if(j-(v[i]+v[son[i][1]])>=0)
                    dp[j]=std::max(dp[j],dp[j-v[i]-v[son[i][1]]]+w[i]+w[son[i][1]]);
                if(j-(v[i]+v[son[i][2]])>=0)
                    dp[j]=std::max(dp[j],dp[j-v[i]-v[son[i][2]]]+w[i]+w[son[i][2]]);
                if(j-(v[i]+v[son[i][2]]+v[son[i][1]])>=0)
                    dp[j]=std::max(dp[j],dp[j-v[i]-v[son[i][1]]-v[son[i][2]]]+w[i]+w[son[i][1]]+w[son[i][2]]);
            }
        }
    }
    printf("%d",dp[m]);
    return 0;
}

by dо_while_true @ 2020-06-07 10:52:27

不同点在于

son[fa][++cnt[fa]]=i;
if(fa)fat[i]++;

改为

if(fa) {
    son[fa][++cnt[fa]]=i;
    fat[i]++;   
}

可能申请的内存是连续的，所以你son[0]越界出去的数会存到son[1]里面，导致的不是RE而是WA

by zjrdmd @ 2020-06-07 10:54:23

@dо_while_true 谢谢神仙，懂了

by zjrdmd @ 2020-06-07 10:54:58

QwQ