【HDOJ】4341 Gold miner

分组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
", 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.
", (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
" % (t))
13         for tt in xrange(t):
14             n = randint(1, 200)
15             T = randint(1, 200**2)
16             fout.write("%d %d
" % (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
" % (x, y, t, v))
23             
24                 
25 def MovDataIn():
26     desFileName = "F:eclipse_prjworkspacehdojdata.in"
27     shutil.copyfile("data.in", desFileName)
28 
29     
30 if __name__ == "__main__":
31     GenDataIn()
32     MovDataIn()