### [题解]ZOJ Monthly, December 2010 » ZOJ3450

ZOJ3450.cpp

```#include <map>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <utility>
#include <algorithm>

using namespace std;

const int MAXT = 10086;

int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}

int dp[MAXT];

void gao(int n, vector<pair<int, pair<int, int> > >& v) {
int t = 0, w = 0;
sort(v.begin(), v.end());
for (vector<pair<int, pair<int, int> > >::iterator it = v.begin(); it != v.end(); ++it) {
t += it->second.first;
w += it->second.second;
it->second.first = t;
it->second.second = w;
//	printf("%d %d\n", t, w);
}
for (int i = n; i >= 0; --i) {
int tmp = dp[i];
for (vector<pair<int, pair<int, int> > >::const_iterator it = v.begin(); it != v.end(); ++it) {
if (i < it->second.first) {
break;
} else {
tmp = max(tmp, dp[i - it->second.first] + it->second.second);
}
}
dp[i] = tmp;
}
}

int main() {
int x0, y0, x, y, z, t, w, n, m;

while (scanf("%d%d%d%d", &x0, &y0, &n, &m) != EOF) {
map<pair<int, int>, vector<pair<int, pair<int, int> > > > mp;

for (int i = 0; i < n; ++i) {
scanf("%d%d%d%d", &x, &y, &t, &w);
x -= x0;
y -= y0;
z = gcd(abs(x), abs(y));
x /= z;
y /= z;
mp[make_pair(x, y)].push_back(make_pair(z, make_pair(t, w)));
}
fill(dp, dp + m + 1, 0);
for (map<pair<int, int>, vector<pair<int, pair<int, int> > > >::iterator it = mp.begin(); it != mp.end(); ++it) {
//	printf("gao (%d, %d)\n", it->first.first, it->first.second);
gao(m, it->second);
}
printf("%d\n", *max_element(dp, dp + m + 1));
}

return 0;
}

//Run ID 	Submit Time 	Judge Status 	Problem ID 	Language 	Run Time(ms) 	Run Memory(KB) 	User Name 	Admin
//631 	2010-12-24 00:08:20 	Accepted 	F 	C++ 	340 	220 	watashi@Zodiac 	Source
```
15 Responses to “ZOJ3450”
1. chenzuying says:

为什么 初始化：dp[0]=0,dp[1..t0]=-inf 和dp[0..t0]=-inf都能过

• watashi says:

那就看你DP转移里面怎么写的了咯……

2. jing says:

跪求测试数据~~~~(>_<)~~~~

• watashi says:

都是generator生成的，你可以自己生成数据，然后和AC的程序对拍

• jing says:

跪求大神qq号码，以求讨论

• watashi says:

530605879

• jing says:

是不是qq号码写错了？5555555

• jing says:

好像是死在什么特殊的地方了，随机化没测出错误来~~~~(>_<)~~~~

• watashi says:

t=0? 其它不知道有什么特殊的地方了
怎么随机的数据，完全rand()的大数据没有点共射线就没有意义了……

• jing says:

觉得月赛好难，又觉得这题目对你好像蛮轻松的，做人绝望了555555555555555555555555555555

• watashi says:

表示不能说轻松，这些题目我暑假都做过了了，也听过作者的讲解了，知根知底后再看题目总是要简单一些
月赛的难度大概是以Regional中等题居多吧
所有人都是一步一步成长的……我做ZOJ Monthly, June 2007 (http://acm.zju.edu.cn/onlinejudge/showContestRankList.do?contestId=208) 的时候，整场就过了一道题，还是找规律过去的……

• jing says:

还是得好好加油，不知大神是什么时候开始A题的，还有，大神，您qq号码是不是写错了？

• jing says:

看来大神还是蛮厉害的，想当年我连a+b这种题wa了n次，后来还是学长帮忙才过的

• jing says:

不知大神做出全部的题花了多少时间？

• daizhenyang says:

一道题都没过的飘

3.