uva 11258 String Partition

uva 11258

把给的字符串拆成32位有符号整形范围内的整数，(1<<30)-1,使它们的和最大，和可以超过int范围

先把全部可能用到的家数都枚举出来，得到sum[i][j]，其中为str[i]到str[j] 构成的数字，再对每个数字加或不加判断最优结果，类似背包，dp[i]为前i位能分出数的最大和

dp[i]=max(dp[i],dp[j]+sum[j+1][i])

#include<stdio.h>
#include<string.h>
#define maxn 210
#define INF (1<<31)-1
long long sum[maxn][maxn];
long long dp[maxn];
char str[maxn];
long long max(long long a,long long b)
{
    return a>b?a:b;
}
int main()
{
    int i,j,k,l,m,n;
    scanf("%d",&l);
    getchar();
    while(l--)
    {
        gets(str+1);
        n=strlen(str+1);
        memset(sum,0,sizeof(sum));
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)
        {
            long long tmp=0;
            for(j=i;j<=n;j++)
            {
                tmp=tmp*10+str[j]-48;
                if(tmp>INF)
                    break;
                sum[i][j]=tmp;
            }
        }
        for(i=1;i<=n;i++)
        {
            for(j=0;j<i;j++)
            {
                dp[i]=max(dp[i],dp[j]+sum[j+1][i]);
            }
        }
        printf("%lld\n",dp[n]);
    }
    return 0;
}