分组01背包。在一条直线上的点归为一组。
1 /* 4341 */
2 #include <iostream>
3 #include <sstream>
4 #include <string>
5 #include <map>
6 #include <queue>
7 #include <set>
8 #include <stack>
9 #include <vector>
10 #include <deque>
11 #include <algorithm>
12 #include <cstdio>
13 #include <cmath>
14 #include <ctime>
15 #include <cstring>
16 #include <climits>
17 #include <cctype>
18 #include <cassert>
19 #include <functional>
20 #include <iterator>
21 #include <iomanip>
22 using namespace std;
23 //#pragma comment(linker,"/STACK:102400000,1024000")
24
25 #define sti set<int>
26 #define stpii set<pair<int, int> >
27 #define mpii map<int,int>
28 #define vi vector<int>
29 #define pii pair<int,int>
30 #define vpii vector<pair<int,int> >
31 #define rep(i, a, n) for (int i=a;i<n;++i)
32 #define per(i, a, n) for (int i=n-1;i>=a;--i)
33 #define clr clear
34 #define pb push_back
35 #define mp make_pair
36 #define fir first
37 #define sec second
38 #define all(x) (x).begin(),(x).end()
39 #define SZ(x) ((int)(x).size())
40 #define lson l, mid, rt<<1
41 #define rson mid+1, r, rt<<1|1
42
43 typedef struct mine_t {
44 int x, y, t, v;
45
46 friend bool operator< (const mine_t& a, const mine_t& b) {
47 int tmp = a.x * b.y - a.y * b.x;
48 if (tmp != 0)
49 return tmp < 0;
50 return a.y < b.y;
51 }
52 } mine_t;
53
54 const int maxn = 205;
55 const int maxt = 40005;
56 mine_t mine[maxn];
57 int dp[maxt];
58 int B[maxn][maxn];
59 int sz[maxn];
60 int n, T;
61
62 bool cmp(int i) {
63 return i+1<n && mine[i].x*mine[i+1].y==mine[i].y*mine[i+1].x;
64 }
65
66 void solve() {
67 int bn = 0;
68
69 sort(mine, mine+n);
70 memset(sz, 0, sizeof(sz));
71 rep(i, 0, n) {
72 B[bn][sz[bn]++] = i;
73 if (cmp(i)) {
74 mine[i+1].t += mine[i].t;
75 mine[i+1].v += mine[i].v;
76 } else {
77 ++bn;
78 }
79 }
80
81 memset(dp, 0, sizeof(dp));
82 rep(i, 0, bn) {
83 per(j, 0, T+1) {
84 rep(k, 0, sz[i]) {
85 int id = B[i][k];
86 int t = mine[id].t;
87 int v = mine[id].v;
88 if (j >= t)
89 dp[j] = max(dp[j], dp[j-t]+v);
90 }
91 }
92 }
93
94 int ans = dp[T];
95 printf("%d\n", ans);
96 }
97
98 int main() {
99 ios::sync_with_stdio(false);
100 #ifndef ONLINE_JUDGE
101 freopen("data.in", "r", stdin);
102 freopen("data.out", "w", stdout);
103 #endif
104
105 int t = 0;
106
107 while (scanf("%d %d", &n, &T) != EOF) {
108 rep(i, 0, n)
109 scanf("%d %d %d %d", &mine[i].x, &mine[i].y, &mine[i].t, &mine[i].v);
110 printf("Case %d: ", ++t);
111 solve();
112 }
113
114 #ifndef ONLINE_JUDGE
115 printf("time = %d.\n", (int)clock());
116 #endif
117
118 return 0;
119 }
数据发生器。
1 from copy import deepcopy
2 from random import randint, shuffle
3 import shutil
4 import string
5
6
7 def GenDataIn():
8 with open("data.in", "w") as fout:
9 t = 20
10 bound = 10**5
11 ld = list(string.digits)
12 # fout.write("%d\n" % (t))
13 for tt in xrange(t):
14 n = randint(1, 200)
15 T = randint(1, 200**2)
16 fout.write("%d %d\n" % (n, T))
17 for i in xrange(n):
18 x = randint(-200, 200)
19 y = randint(0, 200)
20 t = randint(1, 200)
21 v = randint(0, 200)
22 fout.write("%d %d %d %d\n" % (x, y, t, v))
23
24
25 def MovDataIn():
26 desFileName = "F:\eclipse_prj\workspace\hdoj\data.in"
27 shutil.copyfile("data.in", desFileName)
28
29
30 if __name__ == "__main__":
31 GenDataIn()
32 MovDataIn()