wa了
查看原帖
wa了
669832
Ewig_Milan楼主2025/1/21 12:02

大佬帮帮忙 谢谢

#include <bits/stdc++.h>
using namespace std;
int s[60], d[60], n, f[60][60], fm[60][60], ans[60], cnt;//s符号 0--+ 1--* 
int work(int ns[], int nd[]) {
	memset(f, 0, sizeof(f));
	memset(fm, 0, sizeof(fm));
	for(int i = 1; i <= n; i++) f[i][i] = nd[i], fm[i][i] = nd[i];
	for(int len = 2; len <= n; len++) {
		for(int l = 1; l + len - 1 <= n; l++) {
			int r = l + len - 1;
			for(int k = l; k < r; k++) {
				f[l][r] = max(max(ns[k] ? fm[l][k] * fm[k + 1][r] : fm[l][k] + fm[k + 1][r], ns[k] ? f[l][k] * f[k + 1][r] : f[l][k] + f[k + 1][r]),
						  max(max(ns[k] ? fm[l][k] * f[k + 1][r] : fm[l][k] + f[k + 1][r], ns[k] ? f[l][k] * fm[k + 1][r] : f[l][k] + fm[k + 1][r]), f[l][r]));
				fm[l][r] = min(min(ns[k] ? fm[l][k] * fm[k + 1][r] : fm[l][k] + fm[k + 1][r], ns[k] ? f[l][k] * f[k + 1][r] : f[l][k] + f[k + 1][r]),
						   min(min(ns[k] ? fm[l][k] * f[k + 1][r] : fm[l][k] + f[k + 1][r], ns[k] ? f[l][k] * fm[k + 1][r] : f[l][k] + fm[k + 1][r]), fm[l][r]));
			}
		}
	}
	return f[1][n];
}
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= 2 * n; i++) {
		if(i & 1) {
			char c;
			cin >> c;
			s[(i >> 1) + 1] = c == 'x';
		} else scanf("%d", &d[i >> 1]);
	}
	for(int delta = 1; delta <= n; delta++) {
		int temps[60], tempd[60];
		for(int i = 1; i < n; i++) temps[i] = s[(i + delta - 1) % n + 1];
		for(int i = 1; i <= n; i++) tempd[i] = d[(i + delta - 2) % n + 1];
		int t = work(temps, tempd);
		if(t > ans[0]) ans[0] = t, cnt = 0, ans[++cnt] = delta;
		else if(t == ans[0]) ans[++cnt] = delta;
	}
	printf("%d\n", ans[0]);
	for(int i = 1; i <= cnt; i++) printf("%d ", ans[i]);
	return 0;
}
2025/1/21 12:02
加载中...