Andrew Stankevich’s Contest #8解题报告 » ZOJ2672

ZOJ2672
ZOJ2672.cpp


// #include <set>
#include <cstdio>
#include <utility>
#include <ext/hash_map>

using namespace std;
using namespace __gnu_cxx;

const int MAXN = 3003;
int a[MAXN];
short dp[MAXN][MAXN];
// set<pair<int, int> > st;	// TLE(0.62s)
// set<pair<int, int> >::const_iterator it;
hash_map<int, int> mp(MAXN);	// TLE(0.15s)
hash_map<int, int>::const_iterator it;
/*
struct Hash {
	static const int mask = 0x7fff;
	int p[32768], q[32768];

	void clear() {
		for (int i = 0; i <= mask; ++i) {
			q[i] = -1;
		}
	}

	int& operator[](int k) {
		int i = k & mask;
		for (int j = 0; q[i] != -1 && p[i] != k; i = (i + 1) & mask) {
			continue;
		}
		p[i] = k;
		return q[i];
	}
} hash;
*/
int main() {
	bool blank = false;
	int n, m;
	pair<int, int> p;

	while (scanf("%d", &n) != EOF) {
		if (blank) {
			puts("");
		} else {
			blank = true;
		}
		for (int i = 0; i < n; ++i) {
			scanf("%d", &a[i]);
			for (int j = i + 1; j < n; ++j) {
				dp[i][j] = 1;
			}
		}

		m = 0;
		p.first = a[0];
		mp.clear();
		for (int i = n - 1; i >= 0; --i) {
			for (int j = i - 1; j >= 0; --j) {
				// int k = a[i] + a[j];
				// it = st.upper_bound(make_pair(k, j));
				it = mp.find(a[j] + a[i]);
				if (it != mp.end()) {
					dp[j][i] = dp[i][it->second] + 1;
				}
				if (dp[j][i] > m) {
					m = dp[j][i];
					p = make_pair(a[j], a[i]);
				}
			}
			mp[a[i]] = i;
		}

		printf("%d\n", m + 1);
		printf("%d", p.first);
		for (int i = 0; i < m; ++i) {
			printf(" %d", p.second);
			p = make_pair(p.second, p.first + p.second);
		}
		puts("");
	}

	return 0;
}
/*
 * MyHash
Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name
2128941 	2010-03-27 16:50:26 	Accepted 	2672 	C++ 	1720 	18056 	watashi@Zodiac
*/
/*
 * hash_map
Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name
2128955 	2010-03-27 16:54:15 	Accepted 	2672 	C++ 	2610 	17800 	watashi@Zodiac
*/
Leave a Reply