样例输出4200求助

jiawenbo @ 2024-07-16 16:22:28

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll V[100000],W[100000],Q[100000];
ll dp[10000][10000];
ll A[100000][3];
int main()
{
    ll n,m;
    scanf("%lld%lld",&m,&n);
    for (ll i = 1; i <= n; i ++)
    {
        scanf("%lld%lld%lld",&V[i],&W[i],&Q[i]);
        if (Q[i])
        {
            A[i][0] ++;
            A[i][A[i][0]] = i;
        }
        W[i] *= V[i];
    }
    for (ll i = 1; i <= n; i ++)
    {
        for (ll j = 1; j <= m; j ++)
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= V[i]) dp[i][j] = max(dp[i][j],dp[i - 1][j - V[i]] + W[i]);
            if (j >= V[i] + V[A[i][1]]) dp[i][j] = max(dp[i][j],dp[i - 2][j - V[i] - V[A[i][1]]] + W[i] + W[A[i][1]]);
            if (j >= V[i] + V[A[i][2]]) dp[i][j] = max(dp[i][j],dp[i - 2][j - V[i] - V[A[i][2]]] + W[i] + W[A[i][2]]);
            if (j >= V[i] + V[A[i][1]] + V[A[i][2]]) dp[i][j] = max(dp[i][j],dp[i - 3][j - V[i] - V[A[i][1]] - V[A[i][2]]] + W[i] + W[A[i][1]] + W[A[i][2]]);
        }
    }
    printf("%lld",dp[n][m]);
    return 0;
}

by yunyu2 @ 2024-08-18 13:26:19

@jiawenbo 我也错这个点上了，为啥啊？（已AC）

by jiawenbo @ 2024-08-19 14:20:49

@yunyu2 我不到啊我不对

by yunyu2 @ 2024-08-19 14:35:50

@jiawenbo 我的AC代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,tmp,ans=0;
    cin>>n>>m;
    bool mai[n+5];
    int val[n+5],imp[n+5],f[n+5];
    vector<int> item[n+5];
    memset(f,-1,sizeof(f));
    for(int i=1;i<=m;i++)
    {
        cin>>val[i]>>imp[i]>>tmp;
        mai[i]=true;
        if(tmp>0)
        {
            item[tmp].push_back(i);
            mai[i]=false;
        }
    }
    f[0]=0;
    for(int i=1;i<=m;i++)
    {
        if(!mai[i])
            continue;
        for(int j=n-1;j>=0;j--)
        {
            if(f[j]==-1||j+val[i]>n)
                continue;
            f[j+val[i]]=max(f[j+val[i]],f[j]+val[i]*imp[i]);
            if(item[i].size()>0&&j+val[i]+val[item[i][0]]<=n)
                f[j+val[i]+val[item[i][0]]]=max(f[j+val[i]+val[item[i][0]]],f[j]+val[i]*imp[i]+val[item[i][0]]*imp[item[i][0]]);
            if(item[i].size()>1&&j+val[i]+val[item[i][1]]<=n)
            {
                f[j+val[i]+val[item[i][1]]]=max(f[j+val[i]+val[item[i][1]]],f[j]+val[i]*imp[i]+val[item[i][1]]*imp[item[i][1]]);
                if(j+val[i]+val[item[i][0]]+val[item[i][1]]<=n)
                    f[j+val[i]+val[item[i][0]]+val[item[i][1]]]=max(f[j+val[i]+val[item[i][0]]+val[item[i][1]]],f[j]+val[i]*imp[i]+val[item[i][0]]*imp[item[i][0]]+val[item[i][1]]*imp[item[i][1]]);
            }
        }
    }
    for(int j=1;j<=n;j++)
        ans=max(ans,f[j]);
    cout<<ans<<endl;
    return 0;
}

但是我不知道我错哪了，重写了一遍就对了