跳至内容
璟雯院
珺璟如晔,雯华若锦
用户工具
登录
站点工具
搜索
工具
显示页面
修订记录
反向链接
最近更改
媒体管理器
网站地图
登录
>
最近更改
媒体管理器
网站地图
您在这里:
start
»
icpc
»
problems
»
luogup8816
icpc:problems:luogup8816
本页面只读。您可以查看源文件,但不能更改它。如果您觉得这是系统错误,请联系管理员。
====== 上升点列 ====== ===== 想法 ===== 需要注意初始状态。''f[i][j]''设立第''i''个点用了''j''个耗点最长距离。需要注意初始时,'' f[i][j] = j+1; '' 将所有的耗点直接连成线。 ===== 代码实现 ===== <code c++> #include <algorithm> #include <cstdio> using namespace std; struct node { int x, y; }; bool cmp1(node a, node b) { return a.x < b.x || (a.x == b.x && a.y < b.y); } int dis(node a, node b) { return abs(a.x - b.x) + abs(a.y - b.y); } const int N = 510; node line[N]; int f[N][N]; // f[i][j] 到第i个点,用了j个耗点 剩多少个耗点 int main() { int n, k; scanf("%d %d", &n, &k); for (int i = 1; i <= n; i++) scanf("%d %d", &line[i].x, &line[i].y); sort(line + 1, line + 1 + n, cmp1); for(int i=1; i<=n; i++) { for(int j=0; j<=k; j++) f[i][j] = j+1; // 初始时,直接把j个点接在前面。 } for (int i = 1; i <= n; i++) { for (int t = 0; t <= k; t++) { for (int j = 1; j < i; j++) { if (line[i].y < line[j].y || dis(line[i], line[j]) - 1 > t) continue; f[i][t] = max(f[i][t], f[j][t-dis(line[i], line[j])+1] + dis(line[i], line[j])); } } } int mx = 0; for (int i = 1; i <= n; i++) { if(mx < f[i][k]) mx = f[i][k]; } printf("%d", mx); return 0; } </code>
/app/www/public/data/pages/icpc/problems/luogup8816.txt
· 最后更改: 2024/03/26 07:53 由
温婕莺
页面工具
显示页面
修订记录
反向链接
回到顶部