NOJ1017 乘积最大动态规划DP

题目描述

给N个数字和正整数K，问用K个乘号和N个数字组成表达式乘积最大是多少

样例输入

4 2

1231

样例输出

解题思路

经人提醒发现是道DP。。。dp[i][j]表示前i个数字用j个乘号得到的最大值

状态转移方程为 dp[i][j] = max(dp[p][j-1]*ans(p,i-1)) (ans(a,b)为数组s[a]到s[b]组成的数)(1<=p

代码如下

#include 
  
   
#include 
   
     using namespace std; const int maxn = 110; int n; int s[maxn]; char tmp[maxn]; long long dp[maxn][maxn];//dp[i][j]表示前i个数字用了j个乘号 i>j /** 状态转移方程 dp[i][j] = max(dp[p][j-1]*ans(p,i-1)) (ans(a,b)为数组s[a]到s[b]组成的数)(1<=p
    
     = start ; i --) { temp += s[i]*a; a *= 10; } return temp; } long long _max(int i,int j)//返回max { long long _tmp = -1; for(int p = 1 ; p < i ; p ++) { if(_tmp < dp[p][j-1]*ans(p,i-1)) _tmp = dp[p][j-1]*ans(p,i-1); } return _tmp; } int main() { int k; scanf("%d%d",&n,&k); scanf("%s",tmp); for(int i = 0 ; i < n ; i ++) { s[i] = tmp[i] - '0'; } //dp初始化 for(int i = 1 ; i <= n ; i ++) dp[i][0] = ans(0,i-1); //dp for(int j = 1 ; j <= k ; j ++) { for(int i = j+1 ; i <= n ;i ++) { dp[i][j] = _max(i,j); } } printf("%I64d\n",dp[n][k]); return 0; }

NOJ1017 乘积最大 动态规划DP