大意不再赘述。
思路:给定一个字符串序列,让d[i]表示前i个字符切割时的最小值,则d[i] = min(d[i], d[i-j]+num),num表示从后往前划分为j长度的数字,这样,就满足了递推的关系。
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <climits> using namespace std; const int MAXN = 1010; const int INF = INT_MAX; typedef long long LL; LL d[MAXN]; char str[MAXN]; LL dp(int n) { for(int i = 1; i <= n; i++) d[i] = -INF; d[0] = 0; for(int i = 1; i <= n; i++) { for(int j = 1; j <= 10 && j <= i; j++) { LL num = 0; for(int k = 0; k < j; k++) { num = num*10 + str[i-j+k] - '0'; if(num >= 0 && num < INF) { d[i] = max(d[i], d[i-j]+num); } } } } return d[n]; } void solve() { scanf("%s", str); int n = strlen(str); printf("%lld\n", dp(n)); } int main() { int T; scanf("%d", &T); while(T--) { solve(); } return 0; }