全RE0分求助！!

caoyifan111 @ 2021-11-25 22:12:33

#include<bits/stdc++.h>
using namespace std;
int n,m,v[62],p[62],q[62],d[61][32001];
int l[62];
int dp(int i,int j){
    if(d[i][j]!=-1)return d[i][j];
    if(j>n)return 0;
    int res;res=dp(i+1,j);
    if(q[i]==0&&j+v[i]<=n){
        l[i]=1;
        res=max(res,dp(i+1,j+v[i])+v[i]*p[i]);
    }
    else if(l[q[i]]==1&&j+v[i]<=n){
        res=max(res,dp(i+1,j+v[i])+v[i]*p[i]);
    }
    d[i][j]=res;
    return res;
}
int main(){
    cin>>n>>m;
    memset(d,-1,sizeof(d));
    for(int i=1;i<=m;i++)cin>>v[i]>>p[i]>>q[i];
    cout<<dp(1,0);
    return 0;
} 

by shiwei06232 @ 2021-11-25 22:34:09

@LogicM 《勤奋》

by shiwei06232 @ 2021-11-25 22:37:39

dp函数里没判断 i 的越界啊

by shiwei06232 @ 2021-11-25 22:38:47

加个

if(i>m)return 0;

by KRTK_JC @ 2021-11-26 21:52:58

曹老师你这代码加了也肯定过不了，这就是01背包变体，我写了四个判断条件和四个动转方程呢

by luoguhandongheng @ 2022-03-28 18:08:37

#include <bits/stdc++.h>
using namespace std;
int n,m,f[33333];
struct node
{
    int v,p;
}t[33333];
vector <int> fu[65];
int main()
{
    cin>>m>>n;
    int idx=0;
    for(int i=1;i<=n;i++)
    {
        int in1,in2,in3;
        cin>>in1>>in2>>in3;
        if(in3==0)
        {
            fu[i].push_back(i);
            t[i].v=in1;
            t[i].p=in2*in1;
        }   
        else
        {
            fu[in3].push_back(i);
            t[i].v=t[fu[in3][0]].v+in1;
            t[i].p=t[fu[in3][0]].p+in2*in1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=m;t[i].p!=0 && j>=t[i].v;j--)
        {
            f[j]=max(f[j],f[j-t[i].v]+t[i].p);
            if(j>=t[i].v+fu[i][1] && fu[i].size()>2)    f[j]=max(f[j],f[j-t[i].v-t[fu[i][1]].v]+t[i].p+t[fu[i][1]].p);
            else if(j>=t[i].v+fu[i][2] && fu[i].size()>3)   f[j]=max(f[j],f[j-t[i].v-t[fu[i][2]].v]+t[i].p+t[fu[i][2]].p);
            else if(j>=t[i].v+fu[i][2]+fu[i][1] && fu[i].size()>3)  
                f[j]=max(f[j],f[j-t[i].v-t[fu[i][2]].v-t[fu[i][1]].v]+t[i].p+t[fu[i][2]].p+t[fu[i][1]].p);
        }
    }
    //for(int i=1;i<=n;i++) cout<<t[i].p<<' ';
    cout<<f[n];
    return 0;
}

```
为啥我也RE，求助dalao

by caoyifan111 @ 2022-10-21 17:25:37

@shiwei06232 dashenhaolihai