60pts求助

CtrlEEE @ 2024-04-08 19:19:44

#include <bits/stdc++.h>
using namespace std;

long long n,m;
long long av[100000],aw[700000],bv[700000][2],bw[700000][2];
long long dp[100000];
bool f[700000];

int main()
{
    cin >> n >> m;

    int x,y,z;
    memset(f,false,sizeof(f));
    int count = 0;
    for (int i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        if (z == 0){ 
            count ++;
            av[count] = x;
            aw[count] = x*y;} 
        else 
        {
            if(f[z] == false){
                bv[z][0] = x;
                bw[z][0] = x*y;
                f[z] = true;
            }
            else {
                bv[z][1] = x;
                bw[z][1] = x*y;
            }
        }
    }

    memset(dp,0,sizeof(dp));

    for (int i = 1; i<=count ;i++)
    {
        for (int j = n; j >= av[i]; j--)
        {
            dp[j] = max(dp[j],dp[j-av[i]]+aw[i]);
            if (j >= av[i] + bv[i][0]) dp[j] = max(dp[j],dp[j-av[i]-bv[i][0]]+aw[i]+bw[i][0]);
            if (j >= av[i] + bv[i][1]) dp[j] = max(dp[j],dp[j-av[i]-bv[i][1]]+aw[i]+bw[i][1]);
            if (j >= av[i] + bv[i][0] + bv[i][1]) dp[j] = max(dp[j],dp[j-av[i]-bv[i][0]-bv[i][1]]+aw[i]+bw[i][0]+bw[i][1]);
        }
    }
    cout << dp[n];
    return 0; 
}

by Enoch2013 @ 2024-04-08 19:37:21

The ans:

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int zv, zp;
    int fv1, fp1;
    int fv2, fp2;
} a[100];
int maxn, n;
int dp[35000];
int main()
{
    std::ios::basic_ios::ios_base::sync_with_stdio(0);
    cin >> maxn >> n;
    int v, p, q;
    for (int i = 1; i <= n; i++)
    {
        cin >> v >> p >> q;
        if (q == 0)
        {
            a[i].zv = v;
            a[i].zp = v * p;
        }
        else
        {
            if (a[q].fp1 == 0)
            {
                a[q].fv1 = v;
                a[q].fp1 = v * p;
            }
            else
            {
                a[q].fv2 = v;
                a[q].fp2 = v * p;
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (a[i].zp == 0)
            continue;
        for (int j = maxn; j >= a[i].zv; j--)
        {
            dp[j] = max(dp[j], dp[j - a[i].zv] + a[i].zp);
            if (a[i].zv + a[i].fv1 <= j)
                dp[j] = max(dp[j], dp[j - a[i].zv - a[i].fv1] + a[i].zp + a[i].fp1);
            if (a[i].zv + a[i].fv2 <= j)
                dp[j] = max(dp[j], dp[j - a[i].zv - a[i].fv2] + a[i].zp + a[i].fp2);
            if (a[i].zv + a[i].fv1 + a[i].fv2 <= j)
                dp[j] = max(dp[j], dp[j - a[i].zv - a[i].fv1 - a[i].fv2] + a[i].zp + a[i].fp1 + a[i].fp2);
        }
    }
    cout << dp[maxn];
    return 0;
}

by Enoch2013 @ 2024-04-08 19:40:09

你动归的方法错了，看一下我的代码就知道了。

by CtrlEEE @ 2024-04-10 18:36:08

@Enoch2013

饿还是没看出啥，不过你的maxn好像是我的n，你的n是我的m

by Enoch2013 @ 2024-04-11 20:45:33

@CtrlEEE YES

by MinLand @ 2024-04-17 13:38:01

来的可能有点迟，这个问题我做的时候也遇到了。你可以把count去掉，用每次判断一下是不是主件，然后就过了。

也不知道怎么回事

by Au_Gold @ 2024-07-07 21:20:07

https://www.luogu.com.cn/discuss/731402 我跟你一样,看这个就能理解了. 把cout换成i或m