加法最大

Description

设有一个长度为n的数字字符串，分成k+1个部份，使其k+1部份相加的和为最大。例如：数字串’340670’，k=1，其加法有
　　3+40670=40673 34+0670=704 340+670=1010 3406+70=3476 34076+0=34076
其最大和为40676。
问题：当数字串和k给出后，找出一个分法使和为最大。

Input

Output

Sample Input

6 1
340670

Sample Output

40673

解题思路

这道题看似简单，但实际上也很简单。这道题不需要用到高精度，只用使用 l o n g long long l o n g long long就可以了。动态转移方程：
f o r ( l o n g l o n g i = 1 ; i < = m ; i + + ) for(long long i=1;i<=m;i++) for(longlongi=1;i<=m;i++)
f o r ( l o n g l o n g j = i + 1 ; j < = n ; j + + ) for(long long j=i+1;j<=n;j++) for(longlongj=i+1;j<=n;j++)
f o r ( l o n g l o n g k = i ; k < j ; k + + ) for(long long k=i;k<j;k++) for(longlongk=i;k<j;k++)
f [ j ] [ i ] = m a x ( f [ k ] [ i − 1 ] ∗ a [ k + 1 ] [ j ] , f [ j ] [ i ] ) ; f[j][i]=max(f[k][i-1]*a[k+1][j],f[j][i]); f[j][i]=max(f[k][i−1]∗a[k+1][j],f[j][i]);

#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,a[10001][10001],f[10001][10001],t;
int main()
{
   
    scanf("%lld%lld%lld",&n,&m,&t);
    for(long long i=n;i>=1;i--)
    {
   
        a[i][i]=t%10;//分解位数
        t/=10;
    }
    for(long long i=2;i<=n;i++)
    {
   
        for(long long j=i-1;j>=1;j--)
		 a[j][i]=a[j][i-1]*10+a[i][i];//求出每个子序列
    }
    for(long long i=1;i<=n;i++)
	 f[i][0]=a[1][i];
    for(long long i=1;i<=m;i++)
     for(long long j=i+1;j<=n;j++)
      for(long long k=i;k<j;k++)
       f[j][i]=max(f[k][i-1]*a[k+1][j],f[j][i]);//动态转移方程
    printf("%lld",f[n][m]);
    return 0;
}