dp 80pts 求助
查看原帖
dp 80pts 求助
759099
kqQwQ楼主2022/11/1 21:51

不明白哪里错了 QwQ,求大佬帮忙看看

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 510, K = 110;

struct Dot {
    int x, y;
} d[N];

int n, k, ans;
int f[N][K];

bool cmp(Dot a, Dot b) {
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) scanf("%d%d", &d[i].x, &d[i].y);
    sort(d+1, d+n+1, cmp);

    // for (int i = 1; i <= n; ++i) printf("%d %d\n", d[i].x, d[i].y);

    for (int i = 0; i <= k; ++i) f[1][i] = i+1;
    for (int i = 2; i <= n; ++i) {
        for (int t = 1; t < i; ++t) {
            if (d[t].y > d[i].y) continue;

            int p = d[i].x - d[t].x + d[i].y - d[t].y - 1;
            for (int j = 0; j <= k; ++j) {
                if (j >= p) f[i][j] = max(f[i][j], f[t][j-p]+p+1);
                else f[i][j] = max(f[i][j], j+1);
            }
        }
    }

    for (int i = 1; i <= n; ++i) ans = max(ans, f[i][k]);
    printf("%d\n", ans);
    system("pause");
    return 0;
}
2022/11/1 21:51
加载中...