计蒜客整数划分问题(区间DP)

xiaoxiao2021-03-01  2

/* dp[i][j]表示到第i个数末尾加入j-1个乘号所得到的最大值 a[i][j]表示数字序列中从第i个数到第j个数连起来的值 */ #include <bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f const int N=35; long long n,a[N][N],dp[N][N]; int s[N]; int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&s[i]); } int f=0; for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ for(int k=i;k<=j;k++){ f=f*10+s[k]; } a[i][j]=f; f=0; } } for(int i=1;i<=n;i++){ dp[i][1]=a[1][i]; } for(int j=2;j<=m;j++){ for(int i=j;i<=n;i++){ for(int k=1;k<i;k++){ dp[i][j]=max(dp[i][j],dp[k][j-1]*a[k+1][i]); } } } printf("%lld",dp[n][m]); return 0; } /* */

 

转载请注明原文地址: https://www.6miu.com/read-3849937.html

最新回复(0)