For help!

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

Right @ 2016-12-31 12:10:56

#include <stdio.h>
#include <string.h>
//#define max(a,b) a>b?a:b;
using namespace std;
int n,m;
int dp[800][48000];
int v[800][50],w[800][50];
int max(int a,int b)
{
    if (a>b)
        return a;
      else 
        return b;  
}
void csh()
{
    int i,c,p,q;
    scanf("%d%d",&n,&m);
    n/=10;
    for (i=1; i<=m; ++i)
    {
        scanf("%d%d%d",&c,&p,&q);
        c/=10;
        if (q==0)
        {
            w[i][0]=c; 
            v[i][0]=c*p;
        }
        else
            if(w[q][1]==0)  //first one
            {
                w[q][1]=c;
                v[q][1]=c*p;
            }
            else   //second one
            {
                w[q][2]=c;
                v[q][2]=c*p;
            }    
    }
}
void pack()
{
    int i,j;
    int a,b,c,d,e;
    a=0; b=0; c=0; d=0; e=0;
    for (i=1; i<=m; ++i)
    {
        for (j=0; j<=n; ++j)
        {
            e=dp[i-1][j];
            if (j>=w[i][0])
                a=dp[i-1][j-w[i][0]]+v[i][0];
            if (j>=w[i][0]+w[i][1])
                b=dp[i-1][j-(w[i][0]+w[i][1])]+v[i][0]+v[i][1]; 
            if (j>=w[i][0]+w[i][2])
                c=dp[i-1][j-(w[i][0]+w[i][2])]+v[i][0]+v[i][2];
            if (j>=w[i][0]+w[i][1]+w[i][2])
                d=dp[i-1][j-(w[i][0]+w[i][1]+w[i][2])]+v[i][0]+v[i][1]+v[i][2];        
            dp[i][j]=max(e,max(a,max(b,max(c,d))));       
        }
    }
}
void print()
{
    int i,j;
    for (i=m-5; i<=m; ++i)
    {
        for (j=n-10; j<=n; ++j)
            printf("%d  ",&dp[i][j]);
        printf("\n");    
    }
}
int main()
{
    memset(dp,0,sizeof(dp));
    csh();
    pack();
    //print();
    printf("%d\n",dp[m][n]*10);
}

|