POJ 1221 UNIMODAL PALINDROMIC DECOMPOSITIONS：整數拆分 DP 計數對稱序列

問題描述

給定 n (≤ 250)，求和為 n 的「單峰回文分解」個數。定義：序列先嚴格遞增後嚴格遞減，且左右對稱。例如 n=5：(5), (1,3,1), (1,1,1,1,1) 共 3 種。

轉化為整數拆分問題

去掉中間峰值，剩餘左右兩側對稱。設峰值為 m，左右各為嚴格遞增序列和為 (n-m)/2。等價於：將 n 拆分為若干部分，最大部分 ≤ m，且... 實際上直接 DP 更簡單。

DP 狀態定義

f[i][j] = 將 i 拆分為若干正整數，且每個數 ≤ j 的方案數（順序無關，即整數分區）。

遞推關係

• f[i][j] = f[i][j-1] + f[i-j][j] (j ≤ i)
• 不使用 j：f[i][j-1]
• 至少用一個 j：f[i-j][j]
• 邊界：f[0][j]=1, f[i][0]=0 (i>0), f[i][1]=1

最終答案計算

枚舉峰值 m (1~n)，剩餘 n-m 必為偶數，設 s = (n-m)/2。左右兩側各為和為 s、最大值 < m 的嚴格遞增序列。對應分區數為 f[s][m-1]。總和：

ans = 1 + Σ_{m=1}^{n-1} f[(n-m)/2][m-1]   (僅當 n-m 為偶數)

初始 1 對應序列 (n) 本身。

完整代碼

#include 
#include 
using namespace std;

const int MAXN = 250;
long long dp[MAXN+1][MAXN+1];

long long f(int m, int n) {  // 和為 m，最大值 ≤ n
    if (dp[m][n] != -1) return dp[m][n];
    if (m == 0) return dp[m][n] = 1;
    if (n == 0) return dp[m][n] = 0;
    if (n == 1) return dp[m][n] = 1;
    if (n > m) return dp[m][n] = f(m, m);
    return dp[m][n] = f(m, n-1) + f(m-n, n);
}

int main() {
    memset(dp, -1, sizeof(dp));
    int n;
    while (scanf("%d", &n) == 1 && n) {
        long long ans = 1;  // (n)
        for (int mid = 1; mid < n; ++mid) {
            if ((n - mid) % 2 == 0) {
                int half = (n - mid) / 2;
                ans += f(half, mid - 1);
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

關鍵點

1. 記憶化遞歸：狀態數 250×250=62500，極小
2. 長整型：結果可能很大，需 long long (__int64)
3. 對稱性利用：只算左半部分，峰值枚舉
4. 邊界 f(0,n)=1：空分區算 1 種

複雜度

• 狀態數：O(n²)
• 每狀態 O(1) 轉移
• 總時間 O(n²)，n=250 瞬間完成