该题是一道区间 DP 的题目, 做了几道区间 DP, 说起来高大上, 也就是 DP 在区间内的形式而已, 核心思想还是要想到转移 -> 规划.
题意是在 n 位数中间加 m 个称号, 使得最终乘积最大.
状态转移方程如下:
dp[i][ j ]=max( dp[ i ][ j ],dp[ k ][ j - 1]*a[ k + 1][ i ])
a[ i ][ j ] 表示第 i 位到第 j 位组成的数, 要预处理一下.
再来说转移方程, 无非两种情况, 加或不加.
在 k 位不加称号, 便是 dp[ i ] [ j ],
如果加了称号, 便是第 k+1 位到 i 位组成的数与 dp [ k ][ j - 1](k 位加了 j-1 个乘号的最大值) 相乘的结果.
在以上两者中取个最大值, 便形成了转移方程.
代码如下:
- #include<iostream>
- #include<string.h>
- #include<algorithm>
- using namespace std;
- #define ll long long
- ll dp[20][20],f,a[25][25];
- int main()
- {
- int t,n,m,i,j,b[25];
- char s[25],k;
- cin>>t;
- while(t--)
- {
- cin>>s>>m;
- n=strlen(s);
- memset(dp,0,sizeof(dp));
- for(i=0;i<n;i++)
- b[i]=s[i]-'0';
- for(i=0;i<n;i++)
- {
- f=0;
- for(j=i;j<n;j++)
- {
- f=f*10+b[j];
- a[i][j]=f;
- }
- }
- for(i=0;i<n;i++)
- dp[i][0]=a[0][i];// 没有乘号时的 dp 值.
- for(i=0;i<n;i++)
- for(k=0;k<i;k++)
- for(j=1;j<m;j++)
- dp[i][j]=max(dp[i][j],dp[k][j-1]*a[k+1][i]);
- cout<<dp[n-1][m-1]<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2586599.html