南阳理工746整数划分(区间dp)

题意：

给出一个数n，划分成m段，求怎么划分让所有段的成乘积最高。

题解：

区间dp。

状态：dp[i][j] 前j个点分成i段乘积的最大值。

这里有一个分解整数子序列的一个函数，自己写了下，发现挺简单。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;
typedef long long lld;
#define oo 0x3f3f3f3f
#define maxn 210+5
lld dp[maxn][maxn];
lld dig[maxn][maxn];
int a[maxn];
int GetGig(lld n)
{
lld temp=n,temp2,x=1;
int len=0;
while(temp)
{
len++;
temp/=10;
x*=10;
}
temp2=n;
for(int i=1;i<=len;i++)
{
temp=temp2%x;
for(int j=len;j>=i;j--)
{
dig[i][j]=temp;
temp/=10;
}
x/=10;
}
return len;
}
int main()
{
lld n,m;
int T;
scanf("%d",&T);
while(T--)
{
cin>>n>>m;
int len=GetGig(n);
memset(dp,0,sizeof dp);
for(int i=1;i<=len;i++)
dp[1][i]=dig[1][i];
for(int i=2;i<=m;i++)
for(int j=i;j<=len;j++)
for(int k=i-1;k<j;k++)
dp[i][j]=max(dp[i][j],dp[i-1][k]*dig[k+1][j]);
cout<<dp[m][len]<<endl;
}
return 0;
}

最后

以上就是追寻棉花糖为你收集整理的南阳理工746整数划分(区间dp)的全部内容，希望文章能够帮你解决南阳理工746整数划分(区间dp)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。