码风良好，悬关求调，有数据

hateful_bug @ 2024-09-20 17:47:18

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

7430

#include<bits/stdc++.h>
using namespace std;
const int N=65;
int n,m,v[N],w[N],f[34010];
vector<int> h[N];
bool pd[N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int k,typ;
        scanf("%d%d%d",&v[i],&k,&typ);
        w[i]=v[i]*k;
        if(typ)
        pd[i]=true,h[typ].push_back(i);//typ de fj
    }
    for(int i=1;i<=m;i++)
    if(!pd[i])
    for(int j=n;j>=v[i];j--)
    {
        f[j]=max(f[j],f[j-v[i]]+w[i]);
        if(h[i].size()==1)
        {
            int a=h[i][0];
            if(j>=v[i]+v[a])
            f[j]=max(f[j],f[j-v[i]-v[a]]+w[i]+w[a]);
        }
        else if(h[i].size()==2)
        {
            int a=h[i][0],b=h[i][1];
            if(j>=v[i]+v[b])
            f[j]=max(f[j],f[j-v[i]-v[b]]+w[i]+w[b]);
            if(j>=v[i]+v[a]+v[b])
            f[j]=max(f[j],f[j-v[i]-v[a]-v[b]]+w[i]+w[a]+w[b]);
        }
    }
    printf("%d",f[n]);
    return 0;
}

by kaoxiangnb666 @ 2024-09-24 22:17:03

有一种情况是选v[a]和v[i]

by kaoxiangnb666 @ 2024-09-24 22:18:25

AC链接

by kaoxiangnb666 @ 2024-09-24 22:18:59

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=65;
int n,m,v[N],w[N],f[34010];
vector<int> h[N];
bool pd[N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int k,typ;
        scanf("%d%d%d",&v[i],&k,&typ);
        w[i]=v[i]*k;
        if(typ)
        pd[i]=true,h[typ].push_back(i);//typ de fj
    }
    for(int i=1;i<=m;i++)
    if(!pd[i])
    for(int j=n;j>=v[i];j--)
    {
        f[j]=max(f[j],f[j-v[i]]+w[i]);
        if(h[i].size()==1)
        {
            int a=h[i][0];
            if(j>=v[i]+v[a])
            f[j]=max(f[j],f[j-v[i]-v[a]]+w[i]+w[a]);
        }
        else if(h[i].size()==2)
        {
            int a=h[i][0],b=h[i][1];
            if(j>=v[i]+v[b])
            f[j]=max(f[j],f[j-v[i]-v[b]]+w[i]+w[b]);
            if(j>=v[i]+v[a]+v[b])
            f[j]=max(f[j],f[j-v[i]-v[a]-v[b]]+w[i]+w[a]+w[b]);
            if(j>=v[i]+v[a])
            f[j]=max(f[j],f[j-v[i]-v[a]]+w[i]+w[a]);
        }
    }
    printf("%d",f[n]);
    return 0;
}

by kaoxiangnb666 @ 2024-09-25 16:52:25

@kaoxiangnb666 dp转移方程
f[j]=max(f[j],f[j-v[i]-v[a]]+w[i]+w[a]);

by kaoxiangnb666 @ 2024-09-28 22:04:42

哥们你过了吗

by hateful_bug @ 2024-10-24 10:39:29

@kaoxiangnb666 额因为你没@我所以我一个月后才看见你【捂脸】，不过已关，非常感谢！