4558184_wa.cpp

来自「部分PKU上的源码」· C++ 代码 · 共 125 行

/*

ax[i]:第i种邮票的面值

need:顾客所需的总价值

answer:最佳方案的种数

p:搜索到第p种方案

x[i]:记录下一种方案中第i种邮票的张数

ans[i]:最佳方案中第i种邮票的张数

sum[i]:搜索到第i种邮票时，所有邮票的总价值

have:标志有没有解，有的话为1,否则为0

kind[i]:搜索到第i种邮票时总的种类数

sumnum[i]:搜索到第i种邮票时总的邮票张数

tmax[i]:搜索到第i种邮票时，最大的面值

maxkind:临时最佳方案的邮票种类

maxvalue:临时最佳方案中邮票的最大面值

maxnum:临时最佳方案中邮票的张数

count:最佳方案中邮票的种类数

n:邮票的种类数

*/

#include<iostream>
using namespace std;
int ax[100],need,answer,p,x[100],ans[100];
int sum[100],have,kind[100],sumnum[100],tmax[100];
int maxkind,maxvalue,maxnum,count,n;
int stop;
void res(int p)
{
	stop++;
    int i,j;
    for(i=0;i<=4;i++)//第p种邮票取的张数
   {
        if(i)kind[p]=kind[p-1]+1;
        else kind[p]=kind[p-1];
        sumnum[p]=sumnum[p-1]+i;
        sum[p]=sum[p-1]+i*ax[p];
        x[p]=i;
        if(i&&ax[p]>tmax[p-1]) tmax[p]=ax[p];else tmax[p]=tmax[p-1];
        if(sum[p]>need) break;
        if(sum[p]<need&&sumnum[p]<4&&p<n) res(p+1);
        if(!i)continue;
        if(sum[p]==need&&sumnum[p]<=4&&p<=n)
        {
            have=1;
            if(maxkind<kind[p])
            {
                answer=1;count=kind[p];
                for(j=1;j<=p;j++) ans[j]=x[j];ans[0]=p;
                maxvalue=tmax[p];
                maxnum=sumnum[p];
                maxkind=kind[p];
            }
            else if(maxkind==kind[p]&&sumnum[p]<maxnum)
            {
                answer=1;count=kind[p];
                for(j=1;j<=p;j++) ans[j]=x[j];ans[0]=p;
                maxvalue=tmax[p];
                maxnum=sumnum[p];
            }
            else if(maxkind==kind[p]&&maxnum==sumnum[p]&&maxvalue<tmax[p])
            {
                answer=1;count=kind[p];
                for(j=1;j<=p;j++) ans[j]=x[j];ans[0]=p;
                maxvalue=tmax[p];
            }
            else if(maxkind==kind[p]&&maxnum==sumnum[p]&&maxvalue==tmax[p])
                answer++;
        }
    }
}
int main()
{
    int i,j,k;i=1;
    while(cin>>ax[i++])
    {
        if(ax[i-1]==0)
        {
            n=i-1;
            while(cin>>need&&need!=0)
            {
				stop=0;
                memset(ans,0,sizeof(ans));
                kind[0]=sumnum[0]=tmax[0]=0;
                maxkind=maxnum=maxvalue=0;
                answer=0;sum[0]=0;have=0;count=0;
                res(1);
                if(have==0) {cout<<need<<" ---- none"<<endl;continue;}
                else if(answer==1)
                {
                    cout<<need<<" ("<<count<<"): ";
                    for(i=1;i<=ans[0];i++)
                        for(j=1;j<=ans[i];j++)
                        {
                            cout<<ax[i];
                            if(i==ans[0]&&j==ans[i])cout<<endl;
                            else cout<<" ";
                        }
                }
                else if(answer>=2)
                    cout<<need<<" ("<<count<<"): tie"<<endl;
				cout<<stop;
            }    
            i=1;
        }
    }
    return 0;
}