pku 3390 打字排列.txt

ACM资料大集合

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <algorithm>
using namespace std;

//PKU 3390 DP
#define NMAX 10005
#define CMAX 103
#define INFI 999999
#define MH make_heap
#define OH pop_heap
#define PH push_heap
#define PB push_back
#define OB pop_back

int f[NMAX][CMAX];
int len[NMAX];
int getmin(int a,int b) {return a<b?a:b;}
void solve(int num,int cnum)
{
	int i,j;
	for(i=0;i<=num;i++)
	{

		for(j=0;j<=cnum;j++)
			f[i][j]=INFI;
	}
	f[0][cnum]=0;
	for(j=0;j<len[1];j++) f[1][j]=cnum*cnum;
	f[1][len[1]]=(cnum-len[1])*(cnum-len[1]);
	for(j=len[1]+1;j<=cnum;j++) f[1][j]=f[1][j-1];
//	for(j=0;j<=cnum;j++) printf("%3d ",f[1][j]);
//	printf("\n");
	for(i=2;i<=num;i++)
	{
		for(j=0;j<=cnum;j++)
		{
			if(j==0) f[i][j]=f[i-1][cnum]+cnum*cnum;
			else
			{
				if(j-len[i]>=len[i-1]+1)
				{
					f[i][j]=getmin(f[i-1][j-len[i]-1]-(cnum-(j-len[i]-1))*(cnum-(j-len[i]-1))+(cnum-j)*(cnum-j),f[i][j-1]);//跟在以前单词的同一行后面
				}
				else if(j-len[i]>=0) f[i][j]=getmin(f[i][j-1],f[i-1][cnum]+(cnum-len[i])*(cnum-len[i]));//另起一行
				else f[i][j]=f[i][j-1];//不可能出现的情况
			}
//			printf("%3d ",f[i][j]);
		}
//		printf("\n");
	}
	printf("%d\n",f[num][cnum]);
}

int main()
{
	int canum,cnum,num,i,j,k;
//	freopen("dp.out","w",stdout);
	scanf("%d",&canum);
	for(i=1;i<=canum;i++)
	{
		scanf("%d %d",&cnum,&num);
		for(j=1;j<=num;j++)
			scanf("%d",&len[j]);
		solve(num,cnum);
	}
	return 0;
}