本地 4号测试数据答案正确,在线IDE答案错误,求求大佬帮忙看看代码
查看原帖
本地 4号测试数据答案正确,在线IDE答案错误,求求大佬帮忙看看代码
687733
Mrlitttttt楼主2022/11/10 18:38
#include<iostream>
#include<string>
using namespace std;
struct Data {
	int len;
	int ans[100];
};
Data dp[45][10];//dp[i][j]前i个数中有j个乘号时的最大值
int num[45];
Data max1(Data a, Data b) {
	if (a.len > b.len)
		return a;
	else if (b.len > a.len)
		return b;
	for (int i = a.len; i >= 1; i--) {
		if (a.ans[i] > b.ans[i])
			return a;
		if (a.ans[i] < b.ans[i])
			return b;
	}
	return b;
}
Data Mulity(Data a, int L, int R) {
	Data b;
	Data ans;
	b.len = R - L + 1;
	int j = 0, i = 0, k = 0;
	for (j = 0; j < 100; j++) {
		b.ans[j] = 0;
		ans.ans[j] = 0;
	}
	k = L;
	for (j = b.len; j > 0; j--) {
		b.ans[j] = num[k];
		k++;
	}
	for (j = 1; j <= a.len; j++) {
		k = j;
		for (i = 1; i <= b.len; i++) {
			ans.ans[k] = ans.ans[k] + a.ans[j] * b.ans[i];
			ans.ans[k + 1] = ans.ans[k + 1] + ans.ans[k] / 10;
			ans.ans[k] = ans.ans[k] % 10;
			k++;
		}
	}
	for (j = 99; j > 0; j--)
		if (ans.ans[j] != 0) {
			ans.len = j;
			break;
		}
	return ans;
}
int main() {
	int N, K;
	cin >> N >> K;
	string s;
	cin >> s;
		int j = 1;
		for (j = 0; j < N; j++) {
			num[j + 1] = s[j] - '0';
		}
		int i = 0, k = 0;
		for (j = 1; j <= N; j++) {
			int flag = 1;
			for (i = j; i > 0; i--) {
				dp[j][0].ans[i] = num[flag];
				flag++;
			}
			dp[j][0].len = j;
		}
		for (i = 2; i <= N; i++) {
			for (j = 1; j <= min(i - 1, K); j++) {
				for (k = j; k < i; k++) {
					Data c = Mulity(dp[k][j - 1], k + 1, i);
					dp[i][j] = max1(dp[i][j], c);
				}
			}
		}
		for (j = dp[N][K].len; j > 0; j--)
			cout << dp[N][K].ans[j];
		return 0;
}

2022/11/10 18:38
加载中...