求助 求dalao指点

mjc24268 @ 2018-11-06 22:31:37

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct node{
    int w;
    int v;
}Main[100],att[100][3];
int f[1000000];
int m,n;
int main(){
    cin>>m>>n;
    int k=0;
    for(int i=1;i<=n;i++){
        int x,y,z;
        cin>>x>>y>>z;
        if(!z){
            Main[++k].w=x;
            Main[k].v=x*y; 
        }
        else{
            if(!att[z][1].w){
                att[z][1].w=x;
                att[z][1].v=x*y;
            }
            else{
                att[z][2].w=x;
                att[z][2].v=x*y;
            }

        }
    }
//  for(int i=1;i<=k;i++){
//      cout<<Main[i].v<<" "<<Main[i].w<<endl;
//          cout<<att[i][1].w<<" "<<att[i][2].w<<" "<<endl; 
//      cout<<"FUCK"<<endl;
//  }
    for(int i=1;i<=k;i++){
        for(int j=m;j>=Main[i].w;j--){
            f[j]=max(f[j],f[j-Main[i].w]+Main[i].v);
            if(j>=Main[i].w+att[i][1].w){
                f[j]=max(f[j],f[j-Main[i].w-att[i][1].w]+att[i][1].v+Main[i].v);
            }
            if(j>=Main[i].w+att[i][2].w){
                f[j]=max(f[j],f[j-Main[i].w-att[i][2].w]+att[i][2].v+Main[i].v);
            }
            if(j>=Main[i].w+att[i][1].w+att[i][2].w){
                f[j]=max(f[j],f[j-Main[i].w-att[i][1].w-att[i][2].w]+att[i][1].v+att[i][2].v+Main[i].v);
            }
        }
    }   
    cout<<f[m]<<endl;
    return 0;
} 

by Mr_浓氨 @ 2018-11-07 10:14:08

#include <bits/stdc++.h>
using namespace std;
int m,n,mw[33333],mv[33333],fw[33333][3],fv[33333][3],f[33333],v,p,q;
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
void write(int a)
{
    if(a>9)
        write(a/10);
    putchar(a%10+'0');
}
int main()
{
    n=read(),m=read();
    for(int i=1; i<=m; i++)
    {
        v=read(),p=read(),q=read();
        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]);
        }
    write(f[n]);
    return 0;
}

by mjc24268 @ 2018-11-07 10:14:11

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

数据