UVA 11258 String Partition：線性 DP 最大化分割和

題目大意

給一個數位字串（長度 ≤200），需將其分割成若干個不含前導零（單個 0 除外）的 32 位有號整數（≤ INT_MAX），使分割後數字之和最大。輸出最大和。

動態規劃

• dp[i]：前 i 個字元能得到的最大和。
• 轉移：枚舉最後一段長度 l（1~10，因 INT_MAX 為 10 位數），若該段合法，dp[i] = max(dp[i], dp[i-l] + val)。
• 初始 dp[0] = 0，其餘 -inf。

代碼實現

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;

const int MAXN = 220;
long long dp[MAXN];
char str[MAXN];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%s", str + 1);
        int len = strlen(str + 1);
        fill(dp, dp + len + 1, 0);
        for (int i = 1; i <= len; ++i) {
            for (int l = 10; l >= 1; --l) { // 從長到短，優先大數
                if (i - l < 0) continue;
                if (l > 1 && str[i-l+1] == '0') continue; // 前導零
                long long val = 0;
                for (int j = i - l + 1; j <= i; ++j) val = val * 10 + str[j] - '0';
                if (val > INT_MAX) continue;
                dp[i] = max(dp[i], dp[i-l] + val);
            }
        }
        printf("%lld\n", dp[len]);
    }
    return 0;
}

關鍵細節

• 長度限制：INT_MAX = 2147483647（10 位），故 l ≤ 10。
• 前導零檢查：長度 > 1 且首字元為 '0' 則非法。
• 用 long long 存儲 dp 與中間值，防止溢位。
• 從長到短枚舉可略微優化（優先嘗試大數）。

複雜度

• 時間：O(N × 10) = O(N)，N ≤ 200。
• 空間：O(N)

範例解析

輸入: 1234554321
輸出: 1234554321  (整個字串即為合法整數)
輸入: 5432112345
輸出: 543211239   (分割為 54321 + 12345? 實際最優分割需 DP 計算)
輸入: 000
輸出: 0