Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

- -多重背包+路径记录500+MS

Posted by Ink213 at 2013-04-16 20:53:58 on Problem 1787
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN=10010;
int f[MAXN], path[5][MAXN];
int p;
void put(int v,int num,int kd)
{
    int i, j;
    if(v*num>=p)
    {
        for(i=v; i<=p; i++)
        {
            if(f[i-v]>=0)
            {
                f[i]=max(f[i-v]+1,f[i]);
                if(f[i]==f[i-v]+1)
                {
                    path[kd][i]=path[kd][i-v]+1;
                    for(j=kd-1; j>0; j--)
                        path[j][i]=path[j][i-v];
                }
            }
        }
        return;
    }
    int k=1;
    while(k<num)
    {
        for(i=p; i>=k*v; i--)
        {
            if(f[i-k*v]>=0)
            {
                f[i]=max(f[i-k*v]+k,f[i]);
                if(f[i]==f[i-k*v]+k)
                {
                    path[kd][i]=path[kd][i-k*v]+k;
                    for(j=kd-1; j>0; j--)
                        path[j][i]=path[j][i-k*v];
                }
            }
        }
        num-=k;
        k*=2;
    }
    for(i=p; i>=num*v; i--)
    {
        if(f[i-num*v]>=0)
        {
            f[i]=max(f[i-num*v]+num,f[i]);
            if(f[i]==f[i-num*v]+num)
            {
                path[kd][i]=path[kd][i-num*v]+num;
                for(j=kd-1; j>0; j--)
                    path[j][i]=path[j][i-num*v];
            }
        }
    }
}
int main()
{
    int i, j, t[5], ct[5]= {0,1,5,10,25};
    while(scanf("%d%d%d%d%d",&p,&t[1],&t[2],&t[3],&t[4])!=EOF)
    {
        if(!p&&!t[1]&&!t[2]&&!t[3]&&!t[4]) break;
        f[0]=0;
        for(i=1; i<=p; i++)
            f[i]=-1;
        for(i=1; i<=4; i++)
        {
            for(j=0; j<=p; j++)
                path[i][j]=0;
            put(ct[i],t[i],i);
        }
        if(f[p]<0)
            printf("Charlie cannot buy coffee.\n");
        else printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",path[1][p],path[2][p],path[3][p],path[4][p]);
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator