这题是不是有些地方有坑

geother @ 2019-02-10 14:33:14

2000 10
500 1 0
400 4 0
300 5 1
400 5 1
200 5 0
500 4 5
400 4 0
320 2 0
410 3 0
400 3 5

by geother @ 2019-02-10 14:33:46

#include<bits/stdc++.h>
#define N 65
using namespace std;
inline int cinn(){
    int x=0,w=0; char ch=0;
    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar();
    return w?-x:x;
}
int m,n,ip[N],cnt,a[N][30],w[N],v[N],fa[N],f[N][100005];
int main(){
    n=cinn();m=cinn();
    for(int i=1;i<=m;i++){
        w[i]=cinn();
        v[i]=cinn();
        fa[i]=cinn();
        if(fa[i]==0){
            a[++cnt][1]=i;
            ip[i]=cnt;
        }
        else{
            a[ip[fa[i]]][0]++;
            a[ip[fa[i]]][a[ip[fa[i]]][0]+1]=i;
        }
    }
    for(int i=1;i<=cnt;i++)
    for(int j=1;j<=n;j++){
        f[i][j]=f[i-1][j];
        if(j>=w[a[i][1]])
        f[i][j]=max(f[i-1][j],f[i-1][j-w[a[i][1]]]+w[a[i][1]]*v[a[i][1]]);
        if(a[i][0]==1){
            if(j>=w[a[i][1]]+w[a[i][2]]) 
            f[i][j]=max(f[i][j],f[i-1][j-w[a[i][1]]-w[a[i][2]]]+w[a[i][1]]*v[a[i][1]]+w[a[i][2]]*v[a[i][2]]);
        }
        if(a[i][0]==2){
            if(j>=w[a[i][1]]+w[a[i][3]])
            f[i][j]=max(f[i][j],f[i-1][j-w[a[i][1]]-w[a[i][3]]]+w[a[i][1]]*v[a[i][1]]+w[a[i][3]]*v[a[i][3]]);
            if(j>=w[a[i][1]]+w[a[i][3]]+w[a[i][2]])
            f[i][j]=max(f[i][j],f[i-1][j-w[a[i][1]]-w[a[i][2]]-w[a[i][3]]]+w[a[i][1]]*v[a[i][1]]+w[a[i][2]]*v[a[i][2]]+w[a[i][3]]*v[a[i][3]]);
        }
    }
    cout<<f[cnt][n]<<endl;
    return 0;
}

by geother @ 2019-02-10 14:38:21

思路我来回想了将近十遍 应该没错```

就是对于每个主件dp
有五种情况
1 用这个主件
2 不用这个主件
3 用主件+附件1
4 用主件+附件2
5 用主件+附件1+附件2

难道这个思路不对 求大佬指正

by AC_Automation @ 2019-02-10 15:23:24

思路是可行的，应该是细节上有小问题

by fenggwsx @ 2021-11-03 22:34:22

您的for(int j=1;j<=n;j++)应该改为for(int j=n;j>=1;j--)，前者是完全背包