Onway

pku 1221   UNIMODAL PALINDROMIC DECOMPOSITIONS
http://acm.pku.edu.cn/JudgeOnline/problem?id=1221
题意：给定一个n，求串里元素之和为n的数字回文串的个数。

这个题目想了我很久，看着所有讨论都说是简单题，想死的心都有。
最后自己还是想不出来，看了人家的DP状态设计才写出来了。

刚开始，总是往一维DP（其实不算DP吧，都没有状态转移的，只是简单的递推而已）里想，
还想出了其他一些结论，只是还不至于能解出这个题，说白了就是，还是没想到。
以下的内容都是参考了网上已经摆放了N久的题解，加上了自己的理解而已。

假设dp[i][j]为：将i这一个数拆分为串里元素均不少于j的回文串的总个数。
对于这种状态设计的理解很重要，至少要理解里面的两个意思：
1，串里元素均不少于j，也就是这些回文串最外面的两个数至少为j。
2，当j=1时，dp[i][j]即表示，元素之和为i的回文串的总个数，因为元素至少都要为1。
 很明显，dp[i][1]包含了dp[i][2]，dp[i][2]又包含了dp[i][3]……。

然后对于dp[i][j]，再分两层理解来设计转移方程：
1，当最外面的两个元素为j的时候，这两个元素之间的其他元素之和就为i-2*j。
 dp[i-2*j][j]里的所有个数只要往两边加上j就变成了dp[i][j]的一部分解。
2，当最外面的两个元素大于j的时候，只要将dp[i][j]加上dp[i][j+1]即可。
 因为dp[i][j+1]包含了dp[i][j+2]。

所以DP方程可以设计为下：

dp[i][j]=dp[i][j+1]+dp[i-2*j][j];

然后是处理这个方程的边界条件。j<=i,当j==i的时候，dp[i][j]==1；

当i-2*j<0的时候，即代表i不能拆分，应直接加0
当i-2*j==0的时候，这时该这么理解，i可以拆分为最外两个元素为j，中间元素为0
即不存在中间元素，这时的回文串只有一个，即(j,j)。所以dp[0][j]应初始化为1

 1#include <iostream>
 2using namespace std;
 3__int64 dp[301][301];  //假设了数组最大的输入为300。
 4int main()
 5{
 6    int i,j;
 7    for(i=1;i<=300;++i)  //初始化，详细见上。
 8    {
 9        dp[0][i]=1;    
10        dp[i][i]=1;
11    }
12    for(i=2;i<=300;++i)
13        for(j=i-1;j>=1;--j)
14        {
15            dp[i][j]=dp[i][j+1]+(i>=2*j?dp[i-2*j][j]:0);
16            //如果不对i-2*j进行判断，会导致数组访问下溢
17        }
18    int n;
19    while(scanf("%d",&n)!=EOF&&n)
20    {
21        printf("%d %I64d\n",n,dp[n][1]);
22    }
23    return 0;
24}
25