题目传送门：luogu P8816 [CSP-J 2022] 上升点列
这是一道简单的 dp 题。
定义到达指两点的曼哈顿距离是 \(1\)。
我们考虑设状态 \(f(i,j)\) 表示考虑结尾是第 \(i\) 个点，增加了 \(j\) 个点的情况。
\(f(i,j) = \max \{f(i,j), f(u,j) + 1\}\) 点 \(u\) 满足 \(u\) 可以被点 \(i\) 到达。
\(f(i,j) = \max \{f(i,j), f(u,j - dis) + dis + 1\}\) 点 \(u\) 满足可以被点 \(i\) 增加 \(dis\) 个点之后到达，且 \(dis < j\)。
答案就是 \(\max \{f(i,j) + k - j\}\)。
轻松ac(bushi
代码（良心马蜂，无压行
点击查看代码
#include <bits/stdc++.h>
namespace hello_world_djh {
template <typename T>
T read() {
T x = 0, f = 1;
char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar())
if (ch == '-')
f = ~f + 1;
for (; ch >= '0' && ch <= '9'; ch = getchar())
x = (x << 3) + (x << 1) + (ch ^ '0');
return x * f;
}
unsigned popcount(unsigned x) {
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);
return x;
}
const int N = 510, K = 110;
int f[N][K], n = read<int>(), k = read<int>();
std::pair <int, int> point[N];
#define x first
#define y second
int main() {
// freopen("out.txt", "w", stdout);
for (int i = 1; i <= n; i++) {
point[i].x = read<int>();
point[i].y = read<int>();
f[i][0] = 1;
}
std::sort(point + 1, point + n + 1);
for (int i = 2; i <= n; i++)
for (int j = 0; j <= k; j++) {
if (j - 1 >= 0)
f[i][j] = std::max(f[i][j], f[i][j - 1]);
for (int u = 1; u < i; u++) {
auto a = point[i];
auto b = point[u];
if (a.x < b.x || a.y < b.y)
continue;
if (abs(a.x - b.x) + abs(a.y - b.y) == 1)
f[i][j] = std::max(f[i][j],
f[u][j] + (abs(a.x - b.x) + abs(a.y - b.y) == 1));
}
for (int u = 1; u < i; u++) {
auto a = point[i];
auto b = point[u];
if (a.x < b.x || a.y < b.y)
continue;
int dis = (a.x - b.x) + (a.y - b.y) - 1;
if (j >= dis)
f[i][j] = std::max(f[i][j], f[u][j - dis] + dis + 1);
}
}
int ans = -1;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= k; j++)
ans = std::max(ans, f[i][j] + k - j);
printf("%d\n", ans);
return 0;
}
};
int main() {
hello_world_djh::main();
return 0;
}