当前位置：首页 > news >正文

小语种网站制作本地wordpress

news 2025/11/6 2:41:58

小语种网站制作,本地wordpress,如何制作图片,百度引擎搜索引擎目录题目传送门算法解析最终代码提交结果尾声题目传送门 [CSP-J 2022] 上升点列 - 洛谷https://www.luogu.com.cn/problem/P8816 算法解析 k 0 且 xi, yi 值域不大时，这题是非常简单的 DP，类似「数字三角形」。记 dp(x,y) 为「以 (x,y) …

题目传送门

算法解析

最终代码

提交结果

尾声

题目传送门

[CSP-J 2022] 上升点列 - 洛谷https://www.luogu.com.cn/problem/P8816

算法解析

k = 0 且 xi, yi 值域不大时，这题是非常简单的 DP，类似「数字三角形」。

记 dp(x,y) 为「以 (x,y) 为终点，最长合法序列的长度」。

则对于所有（已经存在的）整点，有：

dp(x,y) = max {dp(x − 1, y), dp(x, y − 1)} + 1

xi, yi 值域比较大时：

可以考虑记 dp(n) 表示「以 n 号点结尾的合法序列，最长能有多长」。

dp(n) = max {dp(i) + 1}

i → n ✓

不会存在环状结构——因为合法序列必须向右、上方发展。

把刚刚的DP改造一下，就是本题正解：

记 dp(n, k) 表示「以 n 号点结尾，已经使用掉了 k 个自由点，获得的收益」。

dp(n,k) = max {dp(i, k − cost) + cost + 1}

i → n ✓

实现细节：本题的求值顺序值得注意，合法路径可能形如 P1 → P3 → P2。

有两种解决方法：

记忆化搜索（记忆化搜索最擅长解决求值顺序混乱的 DP）
预先按 x, y 排序，使得编号大的点一定是从编号小的点转移过来

这里记忆化搜索比较好写一些，我这里就只讲记忆化搜索了

先写一下求 a 到 b 需要补多少个点的函数，即两点曼哈顿距离再减一（a 在左下，b 在右上，否则返回无穷）

代码中 x[u] 表示 u 点的横坐标，y[u] 表示 u 点的纵坐标

int dis(int a, int b) {if(x[a] > x[b])return inf;if(y[a] > y[b])return inf;return x[b] - x[a]  + y[b] - y[a] - 1;
}

然后是 dp 函数，定义上面已经说过了

int dp(int now, int k)

首先判断如果自由点已经用完了，即 k < 0，那么返回负无穷（因为最后是取最大值）

int dp(int now, int k) {if(k < 0)return -inf;
}

既然是记忆化，那么就需要记忆

用 vis[n][k] 数组记录 dp(n, k) 是否访问过，val[n][k] 数组记录如果访问过的 dp(n, k) 的值

这样如果 vis[now][k] == true（访问过），则返回 val[now][k]

int dp(int now, int k) {if(k < 0)return -inf;if(vis[now][k])return val[now][k];
}

然后就该枚举它的前驱（代码中的 to），然后取里面最大的收益

这个记录最大收益的变量（代码中的 res）的初值一定要是 1，因为如果哪也去不了，那么就只能走到现在这一个点，也就是 now

int dp(int now, int k) {if(k < 0)return -inf;if(vis[now][k])return val[now][k];int res = 1;for(int to = 1; to <= n; ++to)return res;
}

接下来需要判断 to != now，然后计算出 to 到 now 需要补多少个点（代码中的 cost）

int dp(int now, int k) {if(k < 0)return -inf;if(vis[now][k])return val[now][k];int res = 1;for(int to = 1; to <= n; ++to)if(to != now) {int cost = dis(to, now);}return res;
}

再判断费用超出运算，就 contunue（如果走不到，dis 就会返回无穷，一定大于 k，所以不用特判走不到）

int dp(int now, int k) {if(k < 0)return -inf;if(vis[now][k])return val[now][k];int res = 1;for(int to = 1; to <= n; ++to)if(to != now) {int cost = dis(to, now);if(cost > k)continue;}return res;
}

接着就是往下递归了，now 变成了 to，预算费用还剩 k - cost，所以传进去是

dp(to, k - cost)

然后长度还需要加上 to 到 now 的距离，即 cost + 1，然后更新最大值（代码里的 res）

代码中的 bemax 函数是把第一个参数赋成两个参数的最大值用的，具体实现方法就是用一个三目运算符

void bemax(int &a, int b) {a = a > b ? a : b;
}

int dp(int now, int k) {if(k < 0)return -inf;if(vis[now][k])return val[now][k];int res = 1;for(int to = 1; to <= n; ++to)if(to != now) {int cost = dis(to, now);if(cost > k)continue;bemax(res, dp(to, k - cost) + cost + 1);}return res;
}

最后再将 vis[now][k] 设成 true，val[now][k] 设成 res

最后 return res 就行了

int dp(int now, int k) {if(k < 0)return -inf;if(vis[now][k])return val[now][k];int res = 1;for(int to = 1; to <= n; ++to)if(to != now) {int cost = dis(to, now);if(cost > k)continue;bemax(res, dp(to, k - cost) + cost + 1);}vis[now][k] = true;val[now][k] = res;return res;
}

主函数里需要枚举 i = 1 ~ n，j = 0 ~ k，然后传进去（n 为点的个数，k 为自由点的个数）

注意长度还需要加上没用的 k - j 个点，然后更新答案（代码中的 ans）

for(int i = 1; i <= n; ++i)for(int j = 0; j <= k; ++j)bemax(ans, dp(i, j) + k - j);

最后输出 ans 即可

最终代码

#include <cstdio>
#define N 1005
using namespace std;const int inf = 0x7fffffff;int n, k;
int x[N], y[N];
bool vis[N][N];
int val[N][N];
int ans;void bemax(int &a, int b) {a = a > b ? a : b;
}int dis(int a, int b) {if(x[a] > x[b])return inf;if(y[a] > y[b])return inf;return x[b] - x[a]  + y[b] - y[a] - 1;
}int dp(int now, int k) {if(k < 0)return -inf;if(vis[now][k])return val[now][k];int res = 1;for(int to = 1; to <= n; ++to)if(to != now) {int cost = dis(to, now);if(cost > k)continue;bemax(res, dp(to, k - cost) + cost + 1);}vis[now][k] = true;val[now][k] = res;return res;
}int main() {scanf("%d%d", &n, &k);for(int i = 1; i <= n; ++i)scanf("%d%d", &x[i], &y[i]);for(int i = 1; i <= n; ++i)for(int j = 0; j <= k; ++j)bemax(ans, dp(i, j) + k - j);printf("%d\n", ans);return 0;
}