90分???

P1064 [NOIP2006 提高组] 金明的预算方案

ZXZ695 @ 2018-10-15 17:25:30

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define R register
#define LL long long int
using namespace std;
const int N=65;
const int M=32000+5;
int n,m,tim,v[N][3],p[N][3],q[N],num[N],a[N][3],b[N][3],f[N][M],ans;
int main(){
    scanf("%d%d",&n,&m);
    for(R int i=1;i<=m;i++){
        scanf("%d%d%d",&v[i][0],&p[i][0],&q[i]);
        if(q[i]>0){
            num[q[i]]++;
            v[q[i]][num[q[i]]]=v[i][0];
            p[q[i]][num[q[i]]]=p[i][0];
        }
    }
    for(R int i=1;i<=m;i++){
        if(!q[i]){tim++;
           a[tim][0]=v[i][0]*p[i][0]+v[i][1]*p[i][1]+v[i][2]*p[i][2];
           a[tim][1]=v[i][0]*p[i][0]+v[i][1]*p[i][1];
           a[tim][2]=v[i][0]*p[i][0]+v[i][2]*p[i][2];
           b[tim][0]=v[i][0]+v[i][1]+v[i][2];
           b[tim][1]=v[i][0]+v[i][1];
           b[tim][2]=v[i][0]+v[i][2];
        }
    }
    for(R int i=1;i<=tim;i++){
        for(R int j=0;j<=n;j++){
            for(R int k=0;k<=2;k++){
            if(j>=b[i][k])
            f[i][j]=max(max(f[i-1][j],f[i][j]),f[i-1][j-b[i][k]]+a[i][k]);
            else f[i][j]=max(f[i-1][j],f[i][j]);
            }
        }
    }
    printf("%d",f[tim][n]);
    return 0;
}

by ZXZ695 @ 2018-10-15 18:00:38

已解决,少考虑一种情况。


|