蒟蒻30求助...
查看原帖
蒟蒻30求助...
734630
justin_jiajia蒟蒻楼主2022/10/6 16:31

用DP做的,大佬帮忙看看哪里不对呗~

#include<iostream>
#include<string.h>
using namespace std;
int dp[14][300005];
// dp[magic][time]
void answer(bool if_ok, int h) {
	if (if_ok) cout << "Yes";
	else cout << "No";

	cout << endl;
	cout << h;
	cout << endl;
	exit(0);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int m, s, t;
	cin >> m >> s >> t;
	int d = 0; //距离
	int tm = 0; //时间

	while (m >= 10) {
		m -= 10;
		d += 60;
		tm++;

		if (d > s) answer(true, tm);

		if (t == tm) answer(false, d);
	}


	memset(dp, 0, sizeof(dp));
	dp[m][tm] = d;

	for (int i = tm + 1; i <= t; i++)
		for (int x = 0; x < 14; x++) {
			if (dp[x][i - 1] > s)
				answer(true, i - 1);

			//cout << "magic:" << x << "|time:" << i << " ";
			dp[x][i] = max(dp[x][i - 1] + 17, dp[x][i - 1]);
			//cout << "dp[" << x << "][" << i << "]:" << dp[x][i];

			if (x < 10)
				dp[x][i] = max(dp[x + 4][i - 1], dp[x][i]);

			if (x >= 10)
				dp[x][i] = max(dp[x - 10][i - 1] + 60, dp[x][i]);
		}

	int maxx = 0;

	for (int j = 0; j < 14; j++) {
		//cout << j <<' '<< t << ' ' << dp[j][t]<< endl;
		if (dp[j][t] > maxx) {
			maxx = dp[j][t];

			if (maxx > s) {
				answer(true, t);
				return 0;
			}
		}
	}

	answer(false, maxx);
	return 0;
}
2022/10/6 16:31
加载中...