-
Notifications
You must be signed in to change notification settings - Fork 3
/
P1003.cpp
59 lines (55 loc) · 1.04 KB
/
P1003.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <cstdio>
#include <cstring>
#define MAXN 1010
using namespace std;
int n, x, y, s, Z, mx;
int c[MAXN], dp[MAXN * 10];
inline int mymin(int a, int b)
{
return a < b ? a : b;
}
inline void read(int &x)
{
x = 0;
char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return ;
}
int main()
{
memset(dp, 0x7f, sizeof dp);
mx = dp[0];
read(n);
Z = 5 * n;
for (int i = 1; i <= n; i++)
{
read(x);
read(y);
c[i] = x - y;
s += c[i];
}
dp[s + Z] = 0;
for (int i = 1; i <= n; i++)
{
if (c[i] < 0)
{
for (int j = Z; j >= -Z; j--)
if (j + 2 * c[i] + Z >= 0) dp[j + Z] = mymin(dp[j + Z], dp[j + 2 * c[i] + Z] + 1);
else break;
}
else if (c[i] > 0)
{
for (int j = -Z; j <= Z; j++)
if (j + 2 * c[i] + Z >= 0) dp[j + Z] = mymin(dp[j + Z], dp[j + 2 * c[i] + Z] + 1);
else break;
}
}
for (int i = Z, j = i; j; i++, j--)
if (dp[i] != mx || dp[j] != mx)
{
printf("%d\n", mymin(dp[i], dp[j]));
return 0;
}
return 0;
}