最后一个点过不去求助
查看原帖
最后一个点过不去求助
648693
12dwqsd楼主2022/5/16 21:36
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;
using LL = long long;
const int N = 100 * 2;

int n;
LL maxv;
char op[N];
LL q[N];
LL dp_max[N][N];
LL dp_min[N][N];
vector<int> works;



int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);


	cin >> n;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			dp_max[i][j] = -1e9;
			dp_min[i][j] = 1e9;

		}
	}
	for (int i = 1; i <= n; i++) {
		cin >> op[i];
		op[i + n] = op[i];
		cin >> q[i];
		q[i + n] = q[i];
		dp_max[i][i] = dp_max[i + n][i + n] = q[i];
		dp_min[i][i] = dp_min[i + n][i + n] = q[i];

	}

	for (int len = 2; len <= n; len++) {
		for (int left = 1; left + len - 1 < 2 * n; left++) {
			int right = left + len - 1;
			for (int k = left; k <= right; k++) {
				if (op[k + 1] == 't') {
					dp_max[left][right] = max(dp_max[left][right], dp_max[left][k] + dp_max[k + 1][right]);
					dp_min[left][right] = min(dp_min[left][right], dp_min[left][k] + dp_min[k + 1][right]);
				}
				else {
					dp_max[left][right] = max(dp_max[left][right], dp_max[left][k] * dp_max[k + 1][right]);
					dp_max[left][right] = max(dp_max[left][right], dp_min[left][k] * dp_min[k + 1][right]);
					dp_max[left][right] = max(dp_max[left][right], dp_max[left][k] * dp_min[k + 1][right]);
					dp_max[left][right] = max(dp_max[left][right], dp_min[left][k] * dp_max[k + 1][right]);

					dp_min[left][right] = min(dp_max[left][right], dp_max[left][k] * dp_max[k + 1][right]);
					dp_min[left][right] = min(dp_max[left][right], dp_min[left][k] * dp_min[k + 1][right]);
					dp_min[left][right] = min(dp_max[left][right], dp_max[left][k] * dp_min[k + 1][right]);
					dp_min[left][right] = min(dp_max[left][right], dp_min[left][k] * dp_max[k + 1][right]);
				}
			}

			if (len == n) {
				if (dp_max[left][right] > maxv) {
					maxv = dp_max[left][right];
					works.clear();
					works.push_back(left);
				}
				else if (dp_max[left][right] == maxv) {
					works.push_back(left);
				}
			}
		}

		
	}

	printf("%ld\n", maxv);

	sort(works.begin(), works.end());
	for (int i = 0; i < works.size(); i++) {
		printf("%ld ", works[i]);
	}
	

	return 0;
}
2022/5/16 21:36
加载中...