样例输出7300求调

bcbgszyzh @ 2024-03-10 22:17:20

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
struct node{
    ll w,v,num;
}a[2000][10];
ll b[2000],f[40010];
int main(){
    //freopen("pob nyiaj siv.in","r",stdin);
    //freopen("pob nyiaj siv.out","w",stdout);
    ll w,n;
    cin>>w>>n;
    ll tot=0;
    for(int i=1;i<=n;++i){
        ll x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        if(!z){
            b[i]=tot+1;
            a[++tot][0].num++;
            a[tot][1].w=x;
            a[tot][1].v=x*y;
        } else{
            ll t=b[z];
            a[t][0].num++;
            a[t][a[t][0].num].w=x+a[t][1].w;
            a[t][a[t][0].num].v=x*y+a[t][1].v;
            if(a[t][0].num==3){
                a[t][0].num++;
                a[t][4].w=a[t][2].w+a[t][3].w-a[t][1].w;
                a[t][4].v=a[t][2].v+a[t][3].v-a[t][1].v;
            }
        }
    }
    for(int i=1;i<=tot;++i){
        for(int j=w;j>=0;--j){
            for(int k=1;k<=a[i][0].num;++k){
                if(j>=a[i][j].w){
                    f[j]=max(f[j],f[j-a[i][k].w]+a[i][k].v);
                }
            }
        }
    }
    printf("%lld",f[w]);
    return 0;
} 

by __Rickysun__ @ 2024-03-11 07:13:45

@bcbgszyzh 马上去上学了，来不及了，我把我代码发给你，你慢慢看：

#include <bits/stdc++.h>
using namespace std;
int v[100][10],p[100][10],dp[50000],n,m;
int main() {
    cin>>n>>m;
    int vi,pi,qi;
    for(int i=1;i<=m;i++){
        cin>>vi>>pi>>qi;
        if(qi==0){
            v[i][0]=vi;
            p[i][0]=vi*pi;
        }else{
            if(p[qi][1]==0){
                v[qi][1]=vi;
                p[qi][1]=vi*pi;
            }else{
                v[qi][2]=vi;
                p[qi][2]=vi*pi;
            }
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=n;j>=v[i][0];j--){
            dp[j]=max(dp[j],dp[j-v[i][0]]+p[i][0]);
            if(j>=v[i][0]+v[i][1]) dp[j]=max(dp[j],dp[j-v[i][0]-v[i][1]]+p[i][0]+p[i][1]);
            if(j>=v[i][0]+v[i][2]) dp[j]=max(dp[j],dp[j-v[i][0]-v[i][2]]+p[i][0]+p[i][2]);
            if(j>=v[i][0]+v[i][1]+v[i][2]) dp[j]=max(dp[j],dp[j-v[i][0]-v[i][1]-v[i][2]]+p[i][0]+p[i][1]+p[i][2]);
        }
    }
    cout<<dp[n];
    return 0;
}

我用的是背包，但我没用结构体，凑合着看吧

by __Rickysun__ @ 2024-03-11 07:14:09

@Rickysun 码风清奇（我）

by bcbgszyzh @ 2024-03-11 17:57:42

怎么修改？

如：请回答：

by bcbgszyzh @ 2024-03-11 17:58:18

@Rickysun

by qishifeng0001 @ 2024-03-14 21:18:25

if(j>=a[i][j].w){

改为

if(j>=a[i][k].w){

试一下

by bcbgszyzh @ 2024-03-14 21:22:33

@qishifeng0001 hack 数据

by qishifeng0001 @ 2024-03-14 21:23:17

@bcbgszyzh 附件可能在主件前出现

by qishifeng0001 @ 2024-03-14 21:29:55

by qishifeng0001 @ 2024-03-15 20:30:37

给下修改后的程序哈：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
struct node{
    ll w,v,num;
}a[2000][10];
ll b[2000],f[40010];

int xi[66],yi[66],zi[66];
int main(){
    //freopen("pob nyiaj siv.in","r",stdin);
    //freopen("pob nyiaj siv.out","w",stdout);
    ll w,n;
    cin>>w>>n;
    ll tot=0;
    for(int i=1;i<=n;++i){
        cin>>xi[i]>>yi[i]>>zi[i];
    }
    for(int i=1;i<=n;++i){
        int x=xi[i],y=yi[i];
        if(!zi[i]){
            a[i][0].num++;
            a[i][1].w=x;
            a[i][1].v=x*y;
        }
    }
    for(int i=1;i<=n;++i){
        int x=xi[i],y=yi[i];
        if(zi[i]){
            ll t=zi[i];
            a[t][0].num++;
            a[t][a[t][0].num].w=x+a[t][1].w;
            a[t][a[t][0].num].v=x*y+a[t][1].v;
            if(a[t][0].num==3){
                a[t][0].num++;
                a[t][4].w=a[t][2].w+a[t][3].w-a[t][1].w;
                a[t][4].v=a[t][2].v+a[t][3].v-a[t][1].v;
            }
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=w;j>=0;--j){
            for(int k=1;k<=a[i][0].num;++k){
                if(j>=a[i][k].w){
                    f[j]=max(f[j],f[j-a[i][k].w]+a[i][k].v);
                }
            }
        }
    }
    printf("%lld",f[w]);
    return 0;
} 

by bcbgszyzh @ 2024-03-15 20:31:06