UVa11258

題敘

http://domen111.github.io/UVa-Easy-Viewer/?11258

想法

定義$DP[i][j]$為 $i$ ~ $j$ 的最佳解
設定轉移式 $DP[i][j] = max(DP[i][j], DP[i][k]+DP[k+1][j])$
其中， $k$ 符合 $i\leq k \leq j$
起初，我們可以假設$DP[i][j]$為 $i$ ~ $j$ 的數值
如果超過INT範圍則設定為0，也就是不會有這樣的可能
接下來針對每個$DP[i][j]$找最大值，答案即為$DP[0][s.size()-1]$

Code

//By Koios1143
#include<bits/stdc++.h>
#define LL long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
using namespace std;
long long n,dp[205][205];
string s;

int str_to_int(int l,int r){
	long long now=0;
	while(l<=r){
		now*=10;
		now+=(s[l]-'0');
		l++;
		if(now>INT_MAX){
			return 0;
		}
	}
	return now;
}

int main(){
	IOS
	cin>>n;
	while(n--){
		cin>>s;
		for(int i=0 ; i<s.size() ; i++){
			for(int j=i ; j<s.size() ; j++){
				dp[i][j]=str_to_int(i,j);
			}
		}
		for(int i=0 ; i<s.size() ; i++){
			for(int j=i ; j<s.size() ; j++){
				for(int k=i ; k<=j ; k++){
					dp[i][j]=max(dp[i][j], dp[i][k]+dp[k+1][j]);
				}
			}
		}
		cout<<dp[0][s.size()-1]<<"\n";
	}
	return 0;
}

複雜度分析

假設s.size()為N
共有 $N^2$ 種狀態，每種狀態轉移複雜度為 $O(N)$，總複雜度$O(N^3)$