/*
刚开始用d[i][j]表示从i到j的最大和,O(n^3)勉强过了。
去网上找题解才知道可以只用d[i]表示1到i个数字的最大和,O(n^2)果然很快
*/
#include <stdio.h> #include <string.h> #define ll long long #define maxn 205 #define inf (1<<31)-1 ll d[maxn][maxn]; int len; char s[maxn]; ll max(ll a,ll b) { if(a>b) return a; else return b; } ll getn(int a,int b) { ll n=0,ba=1; for(int i=b;i>=a;i--) { n+=(s[i]-'0')*ba; ba*=10; } return n; } void dp() { for(int i=0;i<len;i++) { for(int j=1;j+i<=len;j++) { ll temp1=getn(j,i+j); if(temp1>inf) break; d[j][j+i]=temp1; } } for(int i=9;i<len;i++) { for(int j=1;j+i<=len;j++) { for(int k=j;k<i+j;k++) { d[j][j+i]=max(d[j][j+i],d[j][k]+d[k+1][j+i]); } } } } int main() { int t; scanf("%d",&t); getchar(); while(t--) { gets(s+1); len=strlen(s+1); memset(d,0,sizeof(d)); dp(); printf("%lld\n",d[1][len]); } return 0; }
#include <stdio.h> #include <string.h> #define ll long long #define maxn 205 #define inf (1<<31)-1 ll d[maxn]; int len; char s[maxn]; ll max(ll a,ll b) { if(a>b) return a; else return b; } ll getn(int a,int b) { ll n=0,ba=1; for(int i=b;i>=a;i--) { n+=(s[i]-'0')*ba; ba*=10; } return n; } void dp() { int i; for(i=1;i<=len;i++) { ll temp=getn(1,i); if(temp>inf) break; d[i]=temp; } for(;i<=len;i++) { for(int j=i;j>1;j--) { ll temp=getn(j,i); if(temp>inf) break; d[i]=max(d[i],d[j-1]+temp); } } } int main() { int t; scanf("%d",&t); getchar(); while(t--) { gets(s+1); len=strlen(s+1); memset(d,0,sizeof(d)); dp(); printf("%lld\n",d[len]); /*for(int i=1;i<=len;i++) printf("%lld\n",d[1][i]);*/ } }