首页 > 代码库 > [CTSC2001] tree
[CTSC2001] tree
拿CTSC的原题出NOIP模拟题真的好吗?
其实挺水的,但是某人报复社会的题面让人望而却步。。。
记忆化搜索,刘老师黑书上说的很详细了。
可以在wikioi上提交。
#include <bits/stdc++.h>#define rep(_i, _j) for(int _i = 1; _i <= _j; ++_i)const int inf = 0x3f3f3f3f;typedef long long LL;typedef double DB;using namespace std;const int maxn = 4 * 31 * 31;const int maxv = maxn;const int maxe = maxv * 3 * 2;int n, base, val[maxn];struct Edge { int edge; int head[maxn], to[maxe], next[maxe]; Edge() { edge = 0; memset(head, -1, sizeof head); } void addedge(int u, int v) { to[edge] = v; next[edge] = head[u]; head[u] = edge++; to[edge] = u; next[edge] = head[v]; head[v] = edge++; }} E;inline int id(int face, int row, int col) { return face * base + col + ((1 + (row - 1) * 2 + 1) * (row) / 2);}void link_face(int a, int b) { for(int i = 0; i < n; ++i) { E.addedge(id(a, i, 0), id(b, i, i * 2)); }}int f[maxn][maxn];int dfs(int fa, int lim) { int &Ranma = f[fa][lim]; if(Ranma != 0) return Ranma; else Ranma = 1; for(int i = E.head[fa]; i != -1; i = E.next[i]) { if((val[fa] < val[E.to[i]] && val[E.to[i]] < lim) || (lim < val[E.to[i]] && val[E.to[i]] < val[fa])) { Ranma = max(Ranma, dfs(E.to[i], lim) + dfs(E.to[i], val[fa])); } } return Ranma;}int main() {#ifndef ONLINE_JUDGE freopen("data.in", "r", stdin); freopen("data.out", "w", stdout);#endif scanf("%d", &n); base = n * n; for(int i = 0; i < 4; ++i) { for(int j = 0; j < n; ++j) { for(int k = 0; k < j * 2 + 1; ++k) { int id_now = id(i, j, k); scanf("%d", &val[id_now]); if(k != 0) { E.addedge(id_now, id(i, j, k - 1)); } if((k & 1) && j != 0) { E.addedge(id_now, id(i, j - 1, k - 1)); } } } } link_face(0, 2), link_face(2, 1), link_face(1, 0); for(int i = 0; i < n; ++i) { E.addedge(id(0, n - 1, i * 2), id(3, n - i - 1, 0)); E.addedge(id(2, n - 1, i * 2), id(3, n - 1, (n - 1) * 2 - i * 2)); E.addedge(id(1, n - 1, i * 2), id(3, i, i * 2)); } int Akane; for(int i = 0; i < 4 * base; ++i) { Akane = max(Akane, dfs(i, 0) + dfs(i, 4 * base + 1) - 1); } printf("%d\n", Akane); return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。