p2p网站开发方法,做网站需要工商证吗,网站建设哪家好?看这里,佛山做网站公司有哪些目录 题目传送门
算法解析
最终代码
提交结果
尾声 题目传送门
[CSP-J 2022] 上升点列 - 洛谷https://www.luogu.com.cn/problem/P8816
算法解析
k 0 且 xi, yi 值域不大时#xff0c;这题是非常简单的 DP#xff0c;类似「数字三角形」。
记 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] 设成 trueval[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 ~ nj 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;
}
提交结果
提交一下哈 ㇏(〃▽〃)㇀ AC ! ! !
尾声
如果这篇博客对您您的团队有帮助的话就帮忙点个赞加个关注
最后祝您您的团队在 OI 的路上一路顺风
┬┴┬┴┤・ω・)ノ Bye~Bye~
