模拟黄金矿工这个游戏，给出每一个金子的位置和所需时间，计算在给定时间内最大收益。
刚看这道题以为金子的位置没什么用，直接DP就行，WA了一发终于明白如果金子和人共线的话只能按顺序抓。
这就是需要考虑先后关系问题。看了背包⑨讲之后以为是“有依赖关系的背包”，感觉解决方案很不明显，想不出来做法。
后来想到，可以把共线的金子按1，1+2，1+2+3。。。变成若干个，然后共线的金子组成一组。
显然这个问题就变成了在组内互斥的情况下的分组DP，背包⑨讲已经给出了伪代码。
预处理的时候使用了优先队列，map，乱搞了一下就好了。。。//好不容易自己写出来了一道不太水的题。。。
1 #include <cstdio>
2 #include <algorithm>
3 #include <cstring>
4 #include <queue>
5 #include <stack>
6 #include <map>
7
8 using namespace std;
9
10 const int maxn = 200+10;
11
12 struct node
13 {
14 int x,y;
15 int w,v;
16 node(){x=0;y=0;w=0;v=0;}
17 node(int x,int y) {w=x;v=y;}
18 bool operator < (const node &b) const
19 {
20 return x*x+y*y > b.x*x+b.y*y;
21 }
22
23 }gold[maxn];
24
25 struct item
26 {
27 int w,v;
28 item(){w=0;v=0;}
29 item(int a,int b){w=a;v=b;}
30 };
31
32 int x[maxn],y[maxn],w[maxn],v[maxn],dp[40010];
33 int N,T;
34 vector <item> itm[maxn];
35
36 int main()
37 {
38 int cas = 1;
39 while(~scanf("%d%d",&N,&T))
40 {
41 map<pair<int,int> , int > mp;
42 priority_queue<node> pq[maxn];
43 int cnt_group = 0;
44 for(int i=0;i<maxn;i++) itm[i].clear();
45
46 for(int i=0,x,y;i<N;i++)
47 {
48 scanf("%d%d%d%d",&gold[i].x,&gold[i].y,&gold[i].w,&gold[i].v);
49 x = gold[i].x;y = gold[i].y;
50
51 if(mp.count(pair<int,int>( x/__gcd(x,y) , y/__gcd(x,y)) ))
52 {
53 pq[mp[pair<int,int>( x/__gcd(x,y) , y/__gcd(x,y))]].push(gold[i]);
54 }
55 else
56 {
57 mp[pair<int,int>( x/__gcd(x,y) , y/__gcd(x,y))]=cnt_group++;
58 pq[mp[pair<int,int>( x/__gcd(x,y) , y/__gcd(x,y))]].push(gold[i]);
59 }
60 }
61
62 map<pair<int,int>,int >::iterator it;
63 node cur;
64 for(int i=0;i<cnt_group;i++)
65 {
66 cur = node(0,0);
67 while(!pq[i].empty())
68 {
69 cur.w += pq[i].top().w;
70 cur.v += pq[i].top().v;
71 pq[i].pop();
72 itm[i].push_back(item(cur.w,cur.v));
73 //printf("grp:%d w:%d v:%d\n",i,cur.w,cur.v);
74 }
75 }
76 memset(dp,0,sizeof dp);
77
78 for(int gp=0;gp<cnt_group;gp++)
79 {
80 int n = itm[gp].size();
81
82 for(int t=T;t>=0;t--)
83 {
84 for(int i=0;i<n;i++) if(t>=itm[gp][i].w)
85 {
86 //printf("t:%d w:%d\n",t,itm[gp][i].w);
87 dp[t] = max(dp[t],dp[t-itm[gp][i].w] + itm[gp][i].v);
88 }
89 }
90 //for(int i=0;i<T;i++)
91 //printf("%d ",dp[i]);
92 //printf("\n");
93 }
94
95 printf("Case %d: %d\n",cas++,dp[T]);
96 }
97 }