8782:乘积最大

【题目描述】

　　　　有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。

【题目链接】

　　　　http://noi.openjudge.cn/ch0206/8782/

【算法】

　　　　决策过程：决策插入第i个乘号的位置使插入乘积最大。状态：前i位插入j个乘号所得乘积的最大值。状态转移方程：dp【i】【j】=max（dp【k】【j-1】*a【k+1】【i】）其中k>=j&&k<i。

　　　　边界：前i位插入0个乘号最大为a【1】【i】。按插入乘号数划分阶段。

【代码】

1 #include <bits/stdc++.h> 2 using namespace std; 3 long long s; 4 int n,k,i,j,m; 5 int dp[50][10],a[50][50]; 6 int main() 7 { 8 scanf("%d%d%lld",&n,&k,&s); 9 for(i=n;i>=1;i--) a[i][i]=s%10,s/=10; 10 for(i=1;i<n;i++) 11 for(j=i+1;j<=n;j++) 12 a[i][j]=a[i][j-1]*10+a[j][j]; 13 for(i=1;i<=n;i++) dp[i][0]=a[1][i]; 14 for(i=1;i<=k;i++) 15 for(j=i+1;j<=n;j++) 16 for(m=i;m<j;m++) 17 dp[j][i]=max(dp[j][i],dp[m][i-1]*a[m+1][j]); 18 printf("%d\n",dp[n][k]); 19 return 0; 20 }

 

转载于:https://www.cnblogs.com/Willendless/p/9381760.html

总结

以上是生活随笔为你收集整理的8782:乘积最大的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。