題目地址
A sequence of positive and non-zero integers called palindromic if it can be read the same forward and backward, for example:

15 2 6 4 6 2 15

20 3 1 1 3 20

We have a special kind of palindromic sequences, let’s call it a special palindrome.

A palindromic sequence is a special palindrome if its values don’t decrease up to the middle value, and of course they don’t increase from the middle to the end.

The sequences above is NOT special, while the following sequences are:

1 2 3 3 7 8 7 3 3 2 1

2 10 2

1 4 13 13 4 1

Let’s define the function F(N), which represents the number of special sequences that the sum of their values is N.

For example F(7) = 5 which are : (7), (1 5 1), (2 3 2), (1 1 3 1 1), (1 1 1 1 1 1 1)

Your job is to write a program that compute the Value F(N) for given N’s.

Input
The Input consists of a sequence of lines, each line contains a positive none zero integer N less than or equal to 250. The last line contains 0 which indicates the end of the input.

Output
Print one line for each given number N, which it the value F(N).

Examples
Input
1
3
7
10
0
Output
1
2
5
17

題目大意：F（n） 就是 數(shù)字總數(shù)等于n，為回文字符串，前面的子串遞增，后面的遞減的字符串的數(shù)量（看一下題目應(yīng)該能懂）。
思路：由于是回文字符串，所有我們只要c處理一邊就行了，數(shù)字是對(duì)半的。如果字符串是長(zhǎng)度是偶數(shù)，那n的數(shù)值必須是偶數(shù)，因?yàn)閮蛇叺目倲?shù)要相等。我們先dp，預(yù)處理出整數(shù)劃分，f[i][j]表示只從1~i中選，且總和等于j的方案數(shù)。然后，我們分字符長(zhǎng)度為偶數(shù)和奇數(shù)處理就行了。

代碼:

#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <cstdlib> #include <stack> #include <vector> #include <set> #include <map> #include <bitset> #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define FILL(a,b) (memset(a,b,sizeof(a))) #define re register #define lson rt<<1 #define rson rt<<1|1 #define lowbit(a) ((a)&-(a)) #define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0); #define fi first #define rep(i,n) for(int i=0;(i)<(n);i++) #define rep1(i,n) for(int i=1;(i)<=(n);i++) #define se secondusing namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int > pii; const ll mod=10001; const ll N =1e6+10; const double eps = 1e-4; const double pi=acos(-1); ll gcd(int a,int b){return !b?a:gcd(b,a%b);} int dx[4]={-1,0,1,0} , dy[4] = {0,1,0,-1}; ll f[351][351]; void solve() {f[1][1] = 1;f[0][0] = 1;for (int i=2;i<=251;i++)for (int j=1;j<=i;j++)f[i][j]=(f[i-1][j-1]+f[i-j][j]);int n;while(cin>>n&&n){ll ans=0;if(n%2==0)//長(zhǎng)度為偶數(shù)的時(shí)候，一邊的總數(shù)必定是n/2；{for(int i=1;i<=n/2;i++) ans+=f[n/2][i];}for(int i=n;i>=1;i-=2)//奇數(shù)時(shí)，枚舉中間那個(gè)數(shù)的值{for(int j=0;j<=i;j++) //因?yàn)橹虚g的數(shù)是最大的，不得超過(guò)中間的數(shù){//cout<<f[(n-i)/2][j]<<endl;ans+=f[(n-i)/2][j];}}cout<<ans<<endl;} } int main() {iosint T;//cin>>T;T=1;while(T--){solve();} }

整數(shù)劃分模板：
狀態(tài)轉(zhuǎn)移方程:
f[i][j] = f[i - 1][j] + f[i][j - i];

const int N = 1010;//一維int n; int f[N];int main() {cin >> n;f[0] = 1;for (int i = 1; i <= n; i ++ )for (int j = i; j <= n; j ++ )f[j] = (f[j] + f[j - i]) ;cout << f[n] << endl;return 0; } const int N = 1010;// 二維int n; int f[N][N];int main() {cin >> n;f[1][1] = 1;for (int i = 2; i <= n; i ++ )for (int j = 1; j <= i; j ++ )f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) ;int res = 0;for (int i = 1; i <= n; i ++ ) res = (res + f[n][i]);cout << res << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的Gym - 100952H--H. Special Palindrome--dp整数划分（模板）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。