Submission #2417866

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <queue>
#include <tuple>
using namespace std;

int dp[32][109][109][109], N, A[109], B[109], C[109];
queue<tuple<int, int, int>>Q;
vector<tuple<int, int, int>>X[5000];

void refresh(int s, int k, int a, int b, int c, int p) {
	if (dp[k][a][b][c] <= p) return;
	dp[k][a][b][c] = p;
	if (s == k) X[p].push_back(make_tuple(a, b, c));
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> A[i] >> B[i] >> C[i];
	for (int i = 0; i <= 31; i++) { for (int j = 0; j <= 108; j++) { for (int k = 0; k <= 108; k++) { for (int l = 0; l <= 108; l++) dp[i][j][k][l] = 10000; } } }

	dp[1][100][A[1]][0] = 0;
	for (int i = 1; i <= N; i++) {
		// 敵から攻撃を受ける
		while (!Q.empty()) Q.pop();
		for (int j = 0; j <= 100; j++) {
			for (int k = 0; k <= 100; k++) {
				for (int l = 0; l <= 100; l++) { if (dp[i][j][k][l] <= 4000) X[dp[i][j][k][l]].push_back(make_tuple(j, k, l)); }
			}
		}
		for (int j = 0; j < 4000; j++) {
			for (int k = 0; k < X[j].size(); k++) {
				int a = get<0>(X[j][k]), b = get<1>(X[j][k]), c = get<2>(X[j][k]);
				if (dp[i][a][b][c] != j) continue;
				Q.push(make_tuple(a, b, c));
			}
			while (!Q.empty()) {
				int a = get<0>(Q.front()), b = get<1>(Q.front()), c = get<2>(Q.front()); Q.pop();
				if (a <= B[i]) continue;

				// 守備
				refresh(i, i, min(100, a - B[i] + 50), min(A[i], b + C[i]), 0, dp[i][a][b][c] + 1);

				// 攻撃
				if (b >= 6) refresh(i, i, a - B[i], min(A[i], b - 5 + C[i]), 0, dp[i][a][b][c] + 1);
				else refresh(i, i + 1, a - B[i], A[i + 1], 0, dp[i][a][b][c] + 1);

				// 連続攻撃
				if (b >= c + 2) refresh(i, i, a - B[i], min(A[i], b - (c + 1) + C[i]), c + 1, dp[i][a][b][c] + 1);
				else refresh(i, i + 1, a - B[i], A[i + 1], c + 1, dp[i][a][b][c] + 1);
			}
		}
	}
	int minx = 10000;
	for (int j = 0; j <= 100; j++) {
		for (int k = 0; k <= 100; k++) {
			for (int l = 0; l <= 100; l++) minx = min(minx, dp[N + 1][j][k][l]);
		}
	}
	if (minx == 10000) minx = -1;
	cout << minx << endl;
	return 0;
}

Submission Info

Judge Result