d.cpp

这是一道典型的动态规划题 提供了三种方法(用C++代码实现)

#include "iostream.h"
#include "string.h"
#include "stdlib.h"
#define Max 200
int a[Max];
int b[Max];
bool ask[Max];
bool asktied[5][Max];
int anst[5][Max];
char ans[4][Max][4];
bool tied[5][Max];
int i,j,k,l,n,m,max,p,q;
int temp;

bool ok(int temp) // there are no maore than 4 stamps value=temp 
{
	int i,j;
	for (i=1,j=0;i<n;i++) if (a[i]==temp) j++;
	return (j<5);
}

int compare(const void * a,const void *b) {return *(int *)a-*(int *)b;}

void work(int oldt,int newt,int oldh,int newh,int l,int j,int k,int p)
{
	int s;
	if (newt<oldt) return;
	if (newt==oldt)
	{
		tied[p+k][l]=true;
		if (ask[l] && newh==oldh) asktied[p+k][l]=true;
		if (newh<=oldh) return;
	}
	else tied[p+k][l]=tied[p][j];
	if (ask[l])	asktied[p+k][l]=tied[p][j];
	//ok;
	anst[p+k][l]=newt;
	memcpy(ans[p+k-1][l],ans[p-1][j],sizeof(ans[p+k-1][l]));
	for (s=0;s<k;s++)	ans[p+k-1][l][p+s]=newh;
}

void main()
{
	for(;;)
	{
		if (cin.eof()) break;
		for (n=0;;) 
		{ 
			if (!(cin>>temp)) break;
			if (ok(temp)) // there are no maore than 4 stamps value=temp 
			{
				a[++n]=temp; 
				if (a[n]==0) break; 
			}
		}
		n--;if (n<=0) break; //end of file
		qsort(a,n+1,sizeof(int),compare);
		memset(ask,false,sizeof(ask));
		for (m=0,max=0;;)
		{
			cin>>b[++m];if (b[m]==0) break;if (b[m]>max) max=b[m];ask[b[m]]=true;
		}
		m--;
		for (j=0;j<=4;j++) for (i=0;i<=max;i++) anst[j][i]=-1;
		anst[0][0]=0;
		memset(ans,0,sizeof(ans));
		memset(tied,false,sizeof(tied));
		memset(asktied,false,sizeof(asktied));
		for (i=1;i<=n;i++)
		{
			for (j=max;j>=0;j--)  
				for (p=0;p<=4;p++) if (anst[p][j]>=0)
					for (k=1;k<=4;k++) if (j+a[i]*k<=max) if (p+k<=4)
					{
						l=j+a[i]*k;
						// work(oldt,newt,oldn,newn,oldh,newh,l);
						work(anst[p+k][l],anst[p][j]+1,ans[p+k-1][l][p-1],a[i],l,j,k,p);
					}
		}
		
		for (i=1;i<=m;i++)
		{
			cout<<b[i]<<' ';
			l=0;p=0;
			for (j=4;j>=1;j--)
			{
				for (k=1;k<=4;k++) if (anst[k][b[i]]==j) {l=j;p=k;break;}
				if (l>0) break;
			}
			if (l==0) {cout<<"---- none\n";continue;}
			cout<<'('<<anst[k][b[i]]<<"): ";
			if (!asktied[k][b[i]]) 
			{
				for (j=1;j<=k;j++) {cout<<(int)ans[k-1][b[i]][j-1];if (j<k) cout<<' ';}
				cout<<endl;
			}
			else cout<<"tie\n";
		}
	}
}