题目链接
题意简述
设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积最大。
同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：
有一个数字串：312， 当N=3，K=1时会有以下两种分法：
-
3*12=36
-
31*2=62
这时，符合题目要求的结果是：31*2=62。
现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。
样例
点击查看样例
分析
本题探讨的是一个序列在区间上的性质，因此用区间DP
最外层枚举用的乘号的个数
用\(dp[i][k]\)表示前\(i\)个数字中使用\(k\)个乘号
然后求前\(k+1,k+2,...,n\)的序列用\(k\)个乘号所能得到的最大值
其中对于前 \(i\) 个字符的序列,用 \(m\) 个乘号相乘时
其最大值的求法是先得到前\(i-1\)个字符用\(m-1\)个乘号的最大值然后枚举第 \(m\) 个乘号的位置(乘号的位置\(\in [m\sim i]\).前 \(i-1\) 个字符用 \(m-1\) 个字符相乘 ,那么 \(i-1 \geq m\))
\(dp[i][k]=max(dp[i][k],dp[j][k-1]*num[j+1][i])\)
预处理:
\(a[i...j]\)表示了\(str[i...j]\)组成的数字
\(dp[i][0]\)即前i个字符用\(0\)个乘号得到的结果,自然是\(a[1][i]\)
代码
点击查看代码
#include<stdio.h>
#include<iostream>
#include<cstdlib>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=20;
LL a[N][N];
LL dp[N][N];
char s[N];
int main()
{
//freopen("uva.txt","r",stdin);
int n,k;
scanf("%d%d",&n,&k);
scanf("%s",s+1);
for(int i = 1;i <= n;i++)
{
a[i][i] = s[i]-'0';
}
for(int i = 1;i <= n;i++)
{
LL t = a[i][i];
for(int j = i+1;j<=n;j++)
{
a[i][j] = t*10 + a[j][j];
t = a[i][j];
// printf("%d %d %lld\n",i,j,a[i][j]);
}
}
for(int i = 1;i <= n;i++)dp[i][0] = a[1][i];
for(int m = 1;m <= k ;m ++)
{
for(int i = m + 1;i <= n ;i++)
{
for(int j = m ;j < i ;j++)
{
dp[i][m] = max(dp[i][m],dp[j][m-1]*a[j+1][i]);
}
}
}
printf("%lld\n",dp[n][k]);
return 0;
}