70分求解

jalawov @ 2016-11-05 15:56:56

#include<cstdio>
#include<iostream>
using namespace std;
int w[61][3]={0};
int v[61][3]={0};
int n,m;
int f[61][30001][5]={0};
int main()
{
    scanf("%d%d",&m,&n);
    int a,b,c;
    for (int i=1;i<=n;i++) {
        scanf("%d%d%d",&a,&b,&c);
        if (c) //读入 
        {
           if (w[c][1]) 
           {
              v[c][2]=a*b;
              w[c][2]=a;
            }
           else 
           {
              v[c][1]=a*b;
              w[c][1]=a;
           }
        }
        else 
        {
           v[i][0]=a*b;
           w[i][0]=a;
        }
    }
    int i,j,k;
    int Max=0;
    for (i=1;i<=n;i++) 
        for (j=1;j<=m;j++) 
        {
            for (k=0;k<5;k++) 
            {
                f[i][j][0]=max(f[i][j][0],f[i-1][j][k]);
                if (j-w[i][0]>=0)
                   f[i][j][1]=max(f[i][j][1],f[i-1][j-w[i][0]][k]+v[i][0]);
                if (j-w[i][0]-w[i][1]>=0)
                   f[i][j][2]=max(f[i][j][2],f[i-1][j-w[i][0]-w[i][1]][k]+v[i][0]+v[i][1]);
                if (j-w[i][0]-w[i][2]>=0)
                   f[i][j][3]=max(f[i][j][3],f[i-1][j-w[i][0]-w[i][2]][k]+v[i][0]+v[i][2]);
                if (j-w[i][0]-w[i][1]-w[i][2]>=0)
                   f[i][j][4]=max(f[i][j][4],f[i-1][j-w[i][0]-w[i][1]-w[i][2]][k]+v[i][0]+v[i][1]+v[i][2]); 
            }
            for (k=0;k<5;k++)
                Max=max(Max,f[i][j][k]);
        }
    printf("%d\n",Max);
    return 0;
}

by __世界第一弱__ @ 2016-11-05 21:23:23

帮你开O3

#include<cstdio>
#include<iostream>
using namespace std;
#define O(x) __attribute__((optimize("-O"#x)))
#define inline O(3)
int w[61][3]={0};
int v[61][3]={0};
int n,m;
int f[61][30001][5]={0};
inline int main()
{
    scanf("%d%d",&m,&n);
    int a,b,c;
    for (int i=1;i<=n;i++) {
        scanf("%d%d%d",&a,&b,&c);
        if (c)
        {
           if (w[c][1]) 
           {
              v[c][2]=a*b;
              w[c][2]=a;
            }
           else 
           {
              v[c][1]=a*b;
              w[c][1]=a;
           }
        }
        else 
        {
           v[i][0]=a*b;
           w[i][0]=a;
        }
    }
    int i,j,k;
    int Max=0;
    for (i=1;i<=n;i++) 
        for (j=1;j<=m;j++) 
        {
            for (k=0;k<5;k++) 
            {
                f[i][j][0]=max(f[i][j][0],f[i-1][j][k]);
                if (j-w[i][0]>=0)
                   f[i][j][1]=max(f[i][j][1],f[i-1][j-w[i][0]][k]+v[i][0]);
                if (j-w[i][0]-w[i][1]>=0)
                   f[i][j][2]=max(f[i][j][2],f[i-1][j-w[i][0]-w[i][1]][k]+v[i][0]+v[i][1]);
                if (j-w[i][0]-w[i][2]>=0)
                   f[i][j][3]=max(f[i][j][3],f[i-1][j-w[i][0]-w[i][2]][k]+v[i][0]+v[i][2]);
                if (j-w[i][0]-w[i][1]-w[i][2]>=0)
                   f[i][j][4]=max(f[i][j][4],f[i-1][j-w[i][0]-w[i][1]-w[i][2]][k]+v[i][0]+v[i][1]+v[i][2]); 
            }
            for (k=0;k<5;k++)
                Max=max(Max,f[i][j][k]);
        }
    printf("%d\n",Max);
    return 0;
}

by __世界第一弱__ @ 2016-11-05 21:24:03

@jalawov