e657 - 11258 - String Partition

🔗 前往 ZeroJudge 原題

題目描述

題目要求將一個數字字串分割成多個非零前導的 32 位有號整數，並計算這些整數的最大總和。允許分割出的整數只有一個前導零。

解題思路

本題可以使用動態規劃 (Dynamic Programming) 解決。dp[i] 表示將字串 s 的前 i+1 個字元分割成整數後的最大總和。 對於每個位置 i，我們嘗試所有可能的分割點 j (從 max(0, i-12) 到 i)，其中 j 表示前一個分割點的位置。 我們提取從 j 到 i 的子字串，並將其轉換為一個整數 tmp。 如果 tmp 超出 32 位有號整數的範圍 (INT_MAX) 或 s[j] 是 '0' (除了單獨的 '0' 之外)，則將 tmp 設為 0。 然後，我們更新 dp[i] 的值：dp[i] = max(dp[j-1] + tmp, dp[i])。如果 j 是 0，則 dp[i] = max(tmp, dp[i])。 最後，dp[sl-1] 儲存了整個字串分割後的最大總和。

複雜度分析

• 時間複雜度: O(n^2)，其中 n 是字串的長度。因為有兩層迴圈，分別迭代字串的每個位置。
• 空間複雜度: O(n)，因為我們使用一個大小為 n+1 的 dp 陣列來儲存中間結果。

程式碼

#include <iostream>
#include <climits>
using namespace std;
long long dp[505],n,sl;
string s;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n;
	while(n--){
		cin >> s;
		for(int i=0;i<501;++i){
			dp[i]=0;
		}
		sl=s.length();
		for(int i=0;i<sl;++i){
			for(int j=max(0,i-12);j<=i;++j){
				long long tmp=0;
				for(int k=j;k<=i;++k){
					tmp*=10;
					tmp+=s[k]-'0';
				}
				if(tmp>INT_MAX||s[j]=='0'){
					tmp=0;
				}
				if(j)dp[i]=max(dp[j-1]+tmp,dp[i]);
				else dp[i]=max(tmp,dp[i]);
			}
		}
		cout << dp[sl-1] << "\n";
	}
}