描述
题解
记得好像和 NYOJ 上边有一道题很像,最大的算式?还是啥我忘了,记得当时自己还没有学动归,所以不是动归过的,数据比较小,大概那时是暴力搞过了吧……
定义一个 dp[i][j] 表示前 i 个字符 j 个乘号的最优解……很水的题。
代码
#include <iostream>
using namespace std;
const int MAXN = 44;
const int MAXK = 10;
int N, K;
int A[MAXN];
int dp[MAXN][MAXK];
int getNum(int st, int ed)
{
int num = 0;
for (int i = st; i <= ed; i++)
{
num *= 10;
num += A[i];
}
return num;
}
int main(int argc, const char * argv[])
{
cin >> N >> K;
for (int i = 1; i <= N; i++)
{
scanf("%1d", A + i);
}
for (int i = 1; i <= N; i++)
{
dp[i][0] = dp[i - 1][0] * 10 + A[i];
}
for (int i = 2; i <= N; i++)
{
for (int j = 1; j <= K; j++)
{
for (int k = j - 1; k < i; k++)
{
dp[i][j] = max(dp[i][j], dp[k][j - 1] * getNum(k + 1, i));
}
}
}
cout << dp[N][K] << '\n';
return 0;
}