poj1221 2010.2.17

poj1221 2010.2.17

题意：

    给一个正整数，求出它的UnimodalPalindromic的个数，所谓的Unimodal Palindromic就是一系列数，单调递增再递减，并且第一个和最后一个数相同，第二个跟倒数第二个数相同，即第i个跟第n-i+1个数相同 

思路：

    完全没思路，感觉跟DP扯不上半点关系，后来网上找了些解题报告研究一下午才搞出来。这个题做得很猥琐。

    把它的UnimodalPalindromic分成两部分：一部分是最小数是j的，就是第一个跟最后一个数等于j的有几个；第二部分是最小数大于j的，可以是j+1，j+2…..的有几个。

   s[i][j]表示和为i，最小数是j的序列的个数。那么第一部分就是s[i-j*2][j],

意思就是和为去掉了首尾两个数后的和，最小数是j；第二部分就是s[i][j+1].最小数大于j的情况的个数。状态转移方程：

s[i][j] = s[i-2*j] + s[i][j+1]

初始化：

①．s[0][j]初始值1.因为当需要调用s[0][j]时，表示拆成了两个相同的数。有一个

②．S[i][j]（i<j）初始值0，不可能的情况

③．S[i][j] (i>=j >i/2) 初始值1，j>i/2时所有s[i][j]都是1，那个就是i本身。

#include <string.h>
#include <stdio.h>

#define N 300

int main()
{
	int i,j;
	int n;
	unsigned int s[N][N];
	memset(s,0,sizeof(s));
	for(i=1;i<N;i++)
		s[0][i]=1;
	for(i=1;i<N;i++)
		for(j=i/2+1;j<=i;j++)
			s[i][j]=1;
	for(i=2;i<N;i++)
		for(j=i/2;j>0;j--)
			s[i][j]=s[i-2*j][j]+s[i][j+1];
	while (scanf("%d",&n),n)
		printf("%d %un",n,s[n][1]);
	return 0;
}

最后

以上就是愉快火为你收集整理的poj1221 2010.2.17的全部内容，希望文章能够帮你解决poj1221 2010.2.17所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。