pku 1221 凸回文数.txt

ACM资料大集合

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iterator>
using namespace std;
#define PB push_back
//PKU 1221 凸回文数

#define NMAX 1000

__int64 f[NMAX][NMAX];//f[i][j],和为i,最外边边界的数字为j时的个数

__int64 cal(int start,int end)
{
	int i,j,sum,k;
	for(i=start+1;i<=end;i++)
	{
		for(j=1;j<=i-1;j++)
		{
			sum=i-2*j;//sum表示除去边界的数，剩下的数的和
			if(sum<0) f[i][j]=0;
			else if(sum==0) f[i][j]=1;
			else
			{
				for(k=j,f[i][j]=0;k<=sum;k++)
					//递归到和为sum时，这里的k是和为sum的数的边界数
					//k要从j（原边界数）开始，因为是凸回文数
					f[i][j]+=f[sum][k];
			}
		}
		f[i][i]=1;
		for(j=1,f[i][0]=0;j<=i;j++) f[i][0]+=f[i][j];
	}
	return f[end][0];
}

int main()
{
	int ttmax=0,num;
	while(1)
	{
		scanf("%d",&num);
		if(num==0) break;
		else
		{
			if(num<=ttmax) printf("%d %I64d\n",num,f[num][0]);
			else 
			{
				printf("%d %I64d\n",num,cal(ttmax,num));
				ttmax=num;
			}
		}
	}
	return 0;
}