文章

20

粉丝

412

获赞

13

访问

165.3k

头像
动态规划:插入乘号问题
推荐阅读
P1835 山东大学机试
发布于2021年4月25日 18:24
阅读数 9.0k

#include <iostream>
using namespace std;

int dp[11][11] = {0}; //dp[i][k]表示前i位数中插入k个乘号的最大值
int a[11][11] = {0}; //a[i][j]表示从第i个数字到第j个数字所组成的j-i+1位整数值 

int main() {
	int n, k, num;
	string s;
	cin >> n >> k;
	cin >> s;
	for(int i = 0;i < n;i++) {
		num = 0;
		for(int j = i;j < n;j++) {
			num = num*10+(s[j]-'0');
			a[i][j] = num;
		}
	}
	for(int i = 0;i < n;i++) {
		dp[i][0] = a[0][i];
	}

	for(int i = 0;i < n;i++) {
		for(int j = 1;j <= k;j++) {
			for(int l = 0;l < i;l++) {
				dp[i][j] = max(dp[l][j-1]*a[l+1][i], dp[i][j]);
			}
		}
	}
	cout << dp[n-1][k] << endl;
    return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发