区间dp—整数划分

50 阅读 0 评论 33 点赞

我是靠谱客的博主无奈豆芽，最近开发中收集的这篇文章主要介绍区间dp—整数划分，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目地址

http://acm.nyist.net/JudgeOnline/problem.php?pid=746

先输入一个整数n，再输入一个数字m，将n分成m - 1 组，使得这m-1组的乘积最大。

代码如下

#include<algorithm>
#include<string.h>
#include<string>
#include<cstdio>
#include<iostream>

using namespace std;

typedef long long ll;

ll func(string s,int l,int r)
{
ll k,ans;

k = 1;
ans = 0;

for(int i = r;i >= l;i --)
{
ans = ans + (s[i] - '0') * k;
k *= 10;
}

return ans;
}

int main()
{
int t,i,j,k,l,m,flag;
string s;
ll ans,dp[50][50],a[50][50];

scanf("%d",&t);
getchar();

while(t --)
{
cin >> s;
cin >> m;

memset(a,0,sizeof(a));
memset(dp,0,sizeof(dp));

for(i = 0;i < s.size();i ++)
{
for(j = i;j < s.size();j ++)
{
a[i][j] = func(s,i,j);
}
}

for(i = 0;i < s.size();i ++)
{
dp[i][0] = a[0][i];
}

for(l = 1;l < m;l ++)
{
for(i = l - 1;i < s.size();i ++)
{
for(k = 0;k < i;k ++)
{
dp[i][l] = max(dp[i][l],dp[k][l - 1] * a[k + 1][i]);
}
}
}

cout<<dp[s.size() - 1][m - 1]<<endl;

}

return 0;
}