首页 > 代码库 > [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;}
View Code