滑雪

/*
f[i][j]:是以(i, j)出发能够滑动的最长距离
*/
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int g[N][N];
int f[N][N];
int n, m;


int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};

int dp(int x, int y) {
    if (f[x][y] != -1)
        return f[x][y];
    f[x][y] = 1;

    for (int i = 0; i < 4; i ++ ) {

        int a = x + dx[i], b = y + dy[i];

        if (a >= 1 && a <= n && b >= 1 && b <= m && g[a][b] < g[x][y])
            f[x][y] = max(f[x][y], dp(a, b) + 1);
    }

    return f[x][y];
}

int main() {
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i ++ )

        for (int j = 1; j <= m; j ++ )

            scanf("%d", &g[i][j]);
    memset(f, -1, sizeof f);
    int res = 0;

    for (int i = 1; i <= n; i ++ )

        for (int j = 1; j <= m; j ++ )

            res = max(res, dp(i, j));
    printf("%d\n", res);
    return 0;
}

Test for Job

/*
f[i]:是以第i个点出发的最大权值和
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

int f[N];
int n, m;
int in[N], w[N];
vector<int> v[N];

int dp(int x) {
    if (f[x] != -INF)
        return f[x];
    f[x] = w[x];
    int ans = -INF;

    for (int i = 0; i < v[x].size(); i ++ ) {

        int temp = dp(v[x][i]);

        if (temp > ans)
            ans = temp;
    }

    if (ans != -INF)
        f[x] += ans;

    return f[x];
}

int main() {
    while (~scanf("%d%d", &n, &m)) {
        for (int i = 1; i <= n; i ++ ) {

            v[i].clear();
            f[i] = -INF;
            in[i] = 0;
        }

        for (int i = 1; i <= n; i ++ )

            scanf("%d", &w[i]);

        while (m -- ) {
            int a, b;
            scanf("%d%d", &a, &b);
            in[b] ++ ;
            v[a].push_back(b);
        }

        int res = -INF;

        for (int i = 1; i <= n; i ++ )

            if (!in[i])
                res = max(res, dp(i));
        printf("%d\n", res);
    }

    return 0;
}

Tiling Up Blocks

/*
f[i][j]:是以(i, j)结尾的最大长度
*/
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int f[N][N];
int num[N][N];
int n;

int dp(int x, int y) {
    if (f[x][y] != -1)
        return f[x][y];
    f[x][y] = num[x][y];
    int ans = 0;

    for (int i = 1; i <= x; i ++ )

        for (int j = 1; j <= y; j ++ )

            if (num[i][j] && !(i == x && j == y))
                ans = max(ans, dp(i, j));

    if (ans != 0)
        f[x][y] += ans;

    return f[x][y];
}

int main() {
    while (~scanf("%d", &n)) {
        if (n == 0) {
            puts("*");
            break;
        }

        memset(num, 0, sizeof num);
        memset(f, -1, sizeof f);
        int max_a = 0, max_b = 0;

        for (int i = 1; i <= n; i ++ ) {

            int a, b;
            scanf("%d%d", &a, &b);
            max_a = max(max_a, a);
            max_b = max(max_b, b);
            num[a][b] ++ ;
        }

        int res = 0;

        for (int i = 1; i <= max_a; i ++ )

            for (int j = 1; j <= max_b; j ++ )

                if (num[i][j])
                    res = max(res, dp(i, j));
        printf("%d\n", res);
    }

    return 0;
}