写下这道题的原因很简单= =，因为这一题的状态转移方程不好找，另一方面，我看到很多针对这一题写的解题报告都把累加状态说得模棱两可，甚至直接说成了一个单一状态，弄得本是菜鸟的我硬生生折磨了一上午画了几个10*10的表才想出来(各种表思路还不一样= =||)
题意：对整数N(N<250)进行划分，划分成单峰回文序列，题目给出K组N，然后求出相应总序列数目。
例如：
1: (1)
2: (2), (1 1)
3: (3), (1 1 1)
4: (4), (1 2 1), (2 2), (1 1 1 1)
5: (5), (1 3 1), (1 1 1 1 1)
6: (6), (1 4 1), (2 2 2), (1 1 2 1 1), (3 3), (1 2 2 1), ( 1 1 1 1 1 1)
7: (7), (1 5 1), (2 3 2), (1 1 3 1 1), (1 1 1 1 1 1 1)
8: (8), (1 6 1), (2 4 2), (1 1 4 1 1), (1 2 2 2 1), (1 1 1 2 1 1 1), ( 4 4),
(1 3 3 1), (2 2 2 2), (1 1 2 2 1 1), (1 1 1 1 1 1 1 1)；
解题思路：
由于给出整数最大可到100+，我们可以想象一下100的整数划分之后的情况数绝对是一个很大的数字了。如果一 一枚举并进行判断无疑会TLE。
但我们可以得出一种递推关系，例如 2.3.4.5.4.3.2 这种由23划分出的序列只要左右加上1就变成了 1.2.3.4.5.4.3.2.1 ，换成2就成为 2.2.3.4.5.4.3.2.2也就是说 27和25划分的部分序列可以根据23划分的部分序列来递推得到。
既然有递推关系且我们可以知道上述单个状态是无后效性的，那么我们就可以用动态规划来完成这一递推
我们简单假设A划分出的序列a1,a2,a3,a2,a1 可推出 由B划分的序列a0,a1,a2,a3,a2,a1,a0
ps: 其中A = B - 2*a0
那么我们递推的两个序列只需要满足a0<=a1即可
我们用DP[A][a1]将A划分出的序列两端数字>=a1的总序列数作为一种状态,这样我们可以得到DP[B][a0]的全部序列了
A中两端数大于i的总序列数
|
因此我们可以找到一个状态转移方程:dp[n][i] = dp[n-i*2][i] + dp[n][i+1];
| |
B中两端数>=i的总序列 B中两端数 >= i+1 的总序列数
因此最终Code为:
//UNIMODAL PALINDROMIC DECOMPOSITIONS
//整数划分 -> 单峰回文序列
//二维DP-状态转移方程挺难想的,要以整数划分后得到的单峰回文序列两端数字>=i为一个状态
//Memory:664K Time:0 Ms
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAX 251
long long dp[MAX][MAX]; //dp[n][i]代表整数为n进行划分时，两端处数字>=i的总情况数
void DP()
{
for (int i = ; i < MAX; i++)
dp[i][i] = ;
for (int i = ; i < MAX; i++)
for (int j = i - ; j >= ; j--)
{
dp[i][j] = dp[i][j + ];
if (i - j * == ) //刚好划分完
dp[i][j]++;
else if (i - j * >= j) //可以继续划分
dp[i][j] += dp[i - j * ][j]; //将i-j*2划分后且两端>=j的状态总数 转移给 i划分后两端为j的状态
}
}
int main()
{
DP();
int n;
while (scanf("%d", &n), n)
printf("%d %lld\n", n, dp[n][]);
return ;
}
小墨原创