Onway

pku 1221   UNIMODAL PALINDROMIC DECOMPOSITIONS
http://acm.pku.edu.cn/JudgeOnline/problem?id=1221
題意：給定一個(gè)n，求串里元素之和為n的數(shù)字回文串的個(gè)數(shù)。

這個(gè)題目想了我很久，看著所有討論都說是簡(jiǎn)單題，想死的心都有。
最后自己還是想不出來，看了人家的DP狀態(tài)設(shè)計(jì)才寫出來了。

剛開始，總是往一維DP（其實(shí)不算DP吧，都沒有狀態(tài)轉(zhuǎn)移的，只是簡(jiǎn)單的遞推而已）里想，
還想出了其他一些結(jié)論，只是還不至于能解出這個(gè)題，說白了就是，還是沒想到。
以下的內(nèi)容都是參考了網(wǎng)上已經(jīng)擺放了N久的題解，加上了自己的理解而已。

假設(shè)dp[i][j]為：將i這一個(gè)數(shù)拆分為串里元素均不少于j的回文串的總個(gè)數(shù)。
對(duì)于這種狀態(tài)設(shè)計(jì)的理解很重要，至少要理解里面的兩個(gè)意思：
1，串里元素均不少于j，也就是這些回文串最外面的兩個(gè)數(shù)至少為j。
2，當(dāng)j=1時(shí)，dp[i][j]即表示，元素之和為i的回文串的總個(gè)數(shù)，因?yàn)樵刂辽俣家獮?。
 很明顯，dp[i][1]包含了dp[i][2]，dp[i][2]又包含了dp[i][3]……。

然后對(duì)于dp[i][j]，再分兩層理解來設(shè)計(jì)轉(zhuǎn)移方程：
1，當(dāng)最外面的兩個(gè)元素為j的時(shí)候，這兩個(gè)元素之間的其他元素之和就為i-2*j。
 dp[i-2*j][j]里的所有個(gè)數(shù)只要往兩邊加上j就變成了dp[i][j]的一部分解。
2，當(dāng)最外面的兩個(gè)元素大于j的時(shí)候，只要將dp[i][j]加上dp[i][j+1]即可。
 因?yàn)閐p[i][j+1]包含了dp[i][j+2]。

所以DP方程可以設(shè)計(jì)為下：

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

然后是處理這個(gè)方程的邊界條件。j<=i,當(dāng)j==i的時(shí)候，dp[i][j]==1；

當(dāng)i-2*j<0的時(shí)候，即代表i不能拆分，應(yīng)直接加0
當(dāng)i-2*j==0的時(shí)候，這時(shí)該這么理解，i可以拆分為最外兩個(gè)元素為j，中間元素為0
即不存在中間元素，這時(shí)的回文串只有一個(gè)，即(j,j)。所以dp[0][j]應(yīng)初始化為1

 1#include <iostream>
 2using namespace std;
 3__int64 dp[301][301];  //假設(shè)了數(shù)組最大的輸入為300。
 4int main()
 5{
 6    int i,j;
 7    for(i=1;i<=300;++i)  //初始化，詳細(xì)見上。
 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            //如果不對(duì)i-2*j進(jìn)行判斷，會(huì)導(dǎo)致數(shù)組訪問下溢
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