2022CSP-J第四题

LiuyiJushi · 2022-11-05 20:35:24 · 个人记录

#include<iostream>
#include<algorithm>
using namespace std;
const int M_N = 10, M_K = 10;
struct node {
    int x, y;
} a[M_N];
int N, K, f[M_N][M_K];
signed main() {
    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        cin >> a[i].x >> a[i].y;
    }
    int answer = K;
    for (int k = 0; k <= K; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (a[j].y > a[i].y || a[j].x > a[i].x) continue;
                int p = a[i].x - a[j].x + a[i].y - a[j].y - 1;
                if(k>=p) f[i][k] = max(f[i][k], f[j][k - p] + p + 1);
            }
            answer = max(f[i][k] + 1 + K - k, answer);
        }
    }
    printf("%d", answer);
}

详解