田忌赛马.cpp

田忌赛马问题：用动态规划问题

#include <stdio.h>
void readdata();
void qsort(int low,int high);
int partition(int low,int high);
void init();
int n,a[100],b[100],l[100][100];
void main()
{
	int i,j;
	readdata();
	init();
	for(i=n-1;i>=1;i--)
	{
		for(j=2;j<n-i+1;j++)
		{
			if(a[i+j]<b[j])
			{
				l[i][j]=l[i][j-1]+1;
			}
			else if(a[i+j]>b[j])
			{
				l[i][j]=l[i+1][j-1]-1;
			}
			else if(l[i+1][j-1]-1>l[i][j-1])
			{
				l[i][j]=l[i+1][j-1]-1;
			}
			else
			{
				l[i][j]=l[i][j-1];
			}
			printf("%d\n",l[1][n-1]);
		}
	}
}
void readdata()
{
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(i=1;i<=n;i++)
	{
		scanf("%d",&b[i]);
	}
}
void init()
{
	int i;
	qsort(1,n);
	for(i=1;i<=n;i++)
	{
		if(a[i]<b[1])
		{
			l[i][0]=1;
		}
		else if(a[i]==b[1])
		{
			l[i][0]=0;
		}
		else
		{
			l[i][0]=-1;
		}
	}
}
int partition(int low,int high)
 {
	 int pivotkey;
	 a[0]=a[low];
	 pivotkey=a[low];
	 while(low<high)
	 {
		 while(low<high&&a[high]<=pivotkey)
		 {
			 --high;
		 }
		 a[low]=a[high];
		 while(low<high&&a[low]>=pivotkey)
		 {
			 ++low;
		 }
		a[high]=a[low];
	 }
	 a[low]=a[0];
	 return low;
 }
int partition1(int low,int high)
 {
	 int pivotkey;
	 b[0]=b[low];
	 pivotkey=b[low];
	 while(low<high)
	 {
		 while(low<high&&b[high]<=pivotkey)
		 {
			 --high;
		 }
		 b[low]=b[high];
		 while(low<high&&b[low]>=pivotkey)
		 {
			 ++low;
		 }
		 b[high]=b[low];
	 }
	 b[low]=b[0];
	 return low;
 }
 void qsort(int low,int high)
{
	int pivotloc,pivotloc1,low1,high1;
	low1=low;
	high1=high;
	if(low<high)
	{
		pivotloc=partition(low,high);
	    qsort(low,pivotloc-1);
		qsort(pivotloc+1,high);
	}
	if(low1<high1)
	{
		pivotloc1=partition1(low1,high1);
	    qsort(low1,pivotloc1-1);
		qsort(pivotloc1+1,high1);
	}
}