MorLeaves @ 2023-08-31 16:47:54

#include<iostream>
#include<cstdio>
using namespace std;
int v[114514],p[114514],q[114514],dp[114514],k[114514]={},fv[114514][233],fp[114514][233];
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&v[i],&p[i],&q[i]);
        if (q[i]==0)
        {
            p[i]*=v[i];
        }
        else
        {
            k[q[i]]++;
            fv[q[i]][k[q[i]]]=v[i];
            fp[q[i]][k[q[i]]]=v[i]*p[i];
        }
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=n;j>=v[i];j--)
        {
            dp[j]=max(dp[j],dp[j-v[i]]+p[i]);
            if (j>=v[i]+fv[i][1])
            {
                dp[j]=max(dp[j],dp[j-v[i]-fv[i][1]]+p[i]+fp[i][1]);
            }
            if (j>=v[i]+fv[i][2])
            {
                dp[j]=max(dp[j],dp[j-v[i]-fv[i][2]]+p[i]+fp[i][2]);
            }
            if (j>=v[i]+fv[i][1]+fv[i][2])
            {
                dp[j]=max(dp[j],dp[j-v[i]-fv[i][1]-fv[i][2]]+p[i]+fp[i][1]+fp[i][2]);
            }
        }
    }
    printf("%d",dp[n]);
    return 0;
}

by BLKzzz @ 2023-08-31 16:55:04

e

by MorLeaves @ 2023-08-31 16:58:45

其实是参考第三篇题解

by MorLeaves @ 2023-08-31 17:04:43

8数据

18000 30

100 3 0

400 5 0

1300 5 1

1400 2 2

500 2 0

800 2 0

1400 5 0

300 5 0

1400 3 0

500 2 0

1800 4 0

400 5 9

1300 5 9

1400 3 0

500 2 0

800 2 0

1400 5 0

300 4 0

1400 3 0

500 2 0

1800 2 0

400 5 20

1300 5 20

1400 3 0

500 2 0

800 5 0

1400 5 0

300 5 0

1400 3 27

500 2 27

数据输出：75800 代码输出：75805

by AlexSong @ 2023-08-31 17:28:49

#include <bits/stdc++.h>
using namespace std;
const int N = 32005;
int n, m, mw[N], mv[N], fw[N][3], fv[N][3], f[N], v, p, q;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i ++) {
        cin >> v >> p >> q;
        if (!q) {
            mw[i] = v;
            mv[i] = v * p;
        }
        else  {
            fw[q][0] ++;
            fw[q][fw[q][0]] = v;
            fv[q][fw[q][0]] = v * p; 
        }
    }
    for (int i = 1; i <= m; i ++) {
        for (int j = n; j >= mw[i]; j --) {
            f[j] = max(f[j], f[j - mw[i]] + mv[i]);
            if (j >= mw[i] + fw[i][1]) f[j] = max(f[j], f[j - mw[i] - fw[i][1]] + mv[i] + fv[i][1]);
            if (j >= mw[i] + fw[i][2]) f[j] = max(f[j], f[j - mw[i] - fw[i][2]] + mv[i] + fv[i][2]);
            if (j >= mw[i] + fw[i][1] + fw[i][2])
                f[j] = max(f[j], f[j - mw[i] - fw[i][1] - fw[i][2]] + mv[i] + fv[i][1] + fv[i][2]);
        }
    }
    cout << f[n] <<endl;
    return 0;
}

by AlexSong @ 2023-08-31 17:36:09

@ikun81401 上面

by MorLeaves @ 2023-08-31 17:38:08

@AlexSong 就是找不出区别

by MorLeaves @ 2023-08-31 17:38:47

@AlexSong 这是第三个题解的代码

by ydkxj @ 2023-08-31 17:53:52

试一下把二维数组改成结构体？ 代码如下，看看？

#include<iostream>
using namespace std;
int dp[100005];
struct st{
    int money,heavy,rt;
}a[1000005];
int mv[100005],mw[1000005];
int cty[10005][3],csz[10005][3];
int main()
{
    int money,n;
    cin>>money>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].money>>a[i].heavy>>a[i].rt;
        if(a[i].rt==0)
        {
             mw[i]=a[i].money;
        mv[i]=a[i].heavy*a[i].money;  
    }  
    else{
        cty[a[i].rt][0]++;   
        cty[a[i].rt][cty[a[i].rt][0]]=a[i].money;
        csz[a[i].rt][cty[a[i].rt][0]]=a[i].heavy*a[i].money;   
    }  
    }  
    for(int i=1;i<=n;i++)
    {
        for(int j=money;j>=mw[i];j--)
        {
            dp[j]=max(dp[j-mw[i]]+mv[i],dp[j]);
            if(j>=mw[i]+cty[i][1])dp[j]=max(dp[j],dp[j-mw[i]-cty[i][1]]+mv[i]+csz[i][1]);  
            if(j>=mw[i]+cty[i][2])dp[j]=max(dp[j],dp[j-mw[i]-cty[i][2]]+mv[i]+csz[i][2]);
            if(j>=mw[i]+cty[i][1]+cty[i][2])dp[j]=max(dp[j],dp[j-mw[i]-cty[i][2]-cty[i][1]]+mv[i]+csz[i][2]+csz[i][1]);

          }  

        }

    cout<<dp[money];
}

by MorLeaves @ 2023-08-31 18:07:32

@ydkxj %%%