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