pku2738.java

这是ACM 方面的资料 是PKU的 北京大学的出来的

import java.io.*;
import java.util.*;
import java.lang.Math;
public class Main
{
	public static void main(String args[]) throws Exception
	{
		Scanner cin=new Scanner(System.in);
		int n,i,k,j,tmp1,tmp2;
		int a[];
		int b[][];
		int t=0;
		while(true)
		{
			n=cin.nextInt();
			if(n==0) break;
			a=new int[n];
			b=new int[n][n];
			for(i=0;i<n;i++)
			{
				for(j=0;j<n;j++) b[i][j]=0;
				a[i]=cin.nextInt();
			}
			for(i=0;i<n-1;i++) b[i][i+1]=Math.abs(a[i]-a[i+1]);
			for(j=3;j<n;j+=2)
			{
				for(i=0,k=i+j;k<n;k++,i++)
				{
					if(a[i+1]>=a[k])
					{
						tmp1=b[i+2][k]+a[i]-a[i+1];
					}
					else
					{
						tmp1=b[i+1][k-1]+a[i]-a[k];
					}
					if(a[i]>=a[k-1])
					{
						tmp2=b[i+1][k-1]+a[k]-a[i];
					}
					else
					{
						tmp2=b[i][k-2]+a[k]-a[k-1];
					}
					b[i][k]=(tmp1>tmp2)?tmp1:tmp2;
				}
			}
			System.out.printf("In game %d, the greedy strategy might lose by as many as %d points.\n",++t,b[0][n-1]);
		}
	}
}