求助,不知道为什么一直 WA
查看原帖
求助,不知道为什么一直 WA
178910
_jhq楼主2021/12/29 21:36

RT,UVA323,调代码吐了,调了很多地方,但是不知道为什么总是 WA WA WA,求助/kel

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define space putchar(' ')
#define enter putchar('\n')
#define debug(x) cerr << #x << " = " << x << endl

namespace Fast
{
	template<typename T> inline void read(T &s)
	{
		s = 0; bool f = false; char c = getchar();
		while (c < '0' || c > '9') { if (c == '-') f = true; c = getchar(); }
		while (c >= '0' && c <= '9') s = (s << 3) + (s << 1) + (c ^ 48), c = getchar();
		if (f) s = ~s + 1;
	}
	template<typename T> inline T Abs(T x) { return x > 0 ? x : -x; }
	template<typename T> inline T Max(T x, T y) { return x > y ? x : y; }
	template<typename T> inline T Min(T x, T y) { return x < y ? x : y; }
	template<typename T> inline T addmod(T &x, T p) { if (x >= p) x -= p; return x; }
	template<typename T> inline T submod(T &x, T p) { if (x < 0) x += p; return x; }
	template<typename T, typename ...Args> inline void read(T& x, Args&... others)
	{
		read(x), read(others...);
	}
	template<typename T, typename ...Args> inline T Max(T x, T y, Args... others)
	{
		return Max(Max(x, y), others...);
	}
	template<typename T, typename ...Args> inline T Min(T x, T y, Args... others)
	{
		return Min(Min(x, y), others...);
	}
}
using namespace Fast;

int d[205], p[205], dp[25][805], pre[205][25][805], ans[205];

int main()
{
	int Case = 0;
	while (true)
	{
		int n, m; read(n, m); if (!n && !m) break;
		memset(dp, 0xcf, sizeof(dp)); memset(pre, 0, sizeof(pre)); dp[0][400] = 0;
		for (int i = 1; i <= n; i++) read(d[i], p[i]);
		for (int i = 1; i <= n; i++)
			for (int j = m; j >= 1; j--)
				for (int k = 0; k <= 800; k++)
				{
					pre[i][j][k] = pre[i - 1][j][k];
					if (k - d[i] + p[i] < 0 || k - d[i] + p[i] > 800) continue;
					int tmp = dp[j - 1][k - d[i] + p[i]] + d[i] + p[i];
					if (dp[j][k] < tmp) dp[j][k] = tmp, pre[i][j][k] = i;
				}
		int i = n, j = m, k = 801, sumd = 0, sump = 0; ans[0] = 0;
		for (int i = 0; i <= 400; i++)
			if (dp[m][400 + i] >= 0) { k = 400 + i; break; }
			else if (dp[m][400 - i] >= 0) { k = 400 - i; break; }
		while (j)
		{
			if (pre[i][j][k] != i) { i = pre[i - 1][j][k]; continue; }
			ans[++ans[0]] = i; sumd += d[i]; sump += p[i];
			int tmp = d[i] - p[i]; i--; j--; k -= tmp;
		}
		printf("Jury #%d\n", ++Case);
		printf("Best jury has value %d for prosecution and value %d for defence:\n", sump, sumd);
		for (int i = ans[0]; i; i--) cout << ' ' << ans[i]; enter; enter;
	}
	return 0;
}
2021/12/29 21:36
加载中...