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;
}