louisfghbvc的部落格

題目連結:  https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/11258.pdf

題目大意:  給你一串數字，問你怎麼切(切的時候數字不能超過32位元)，能夠使得數字總和最大。

思路:  DP, 每個位置開始往後延伸，每次都切看看，並記憶化搜索。

代碼:  

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

string s;
LL dp[250];
LL dfs(int i){
    if(i == s.size()) return 0;
    if(dp[i] != -1) return dp[i];

    LL res = 0, sum = 0;
    // enum split point
    for(int j = i; j < s.size(); ++j){
        sum = sum * 10 + s[j] - '0';
        if(sum > INT_MAX) break;
        res = max(res, sum + dfs(j+1));
    }
    return dp[i] = res;
}

void solve(){
    memset(dp, -1, sizeof dp);
    cin >> s;
    cout << dfs(0) << "\n";
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    int n;
    cin >> n;
    while(n--)
        solve();
}