首页 > 其他分享 >P8816 [CSP-J 2022] 上升点列

P8816 [CSP-J 2022] 上升点列

时间:2023-10-02 09:23:25浏览次数:38  
标签:P8816 个点 int 添加 n1 n2 CSP 点列

Problem

考察算法:\(DP\)。

题目简述

给你 \(n\) 个点,每个点有一个坐标 \((x_i,y_i)\),还可以添加 \(k\) 个点。

添加之后,求:最长的上升点列的长度。

上升点列定义(两个点满足其中之一即可):

  • \(x_{i+1}-x_{i} = 1,y_i = y_{i + 1}\)
  • \(y_{i+1} - y_{i} = 1,x_i = x_{i + 1}\)

思路

设二维数组 \(f[i][j]\) 表示以第 \(i\) 个坐标结尾,增加 \(j\) 个点后最长上升点列的长度。

边界条件

如果每个点不和其他任何点连接,添加 \(j\) 个点后,上升点列的长度也最少是 \(j + 1\)。

注意:\(j\) 的循环范围是 \(0 \to k\)。

$ f[i][j] = j + 1$。

状态转移方程设计

设变量 \(t\) 为当前枚举到的左下方的点(状态的转移只能来自左下方),变量 \(c\) 为如果要连接 \(i\) 点和 \(t\) 点,最少要添加多少个点。

变量 \(c\) 如何计算:曼哈顿距离。\(c = (x_i-x_t) + (y_i - y_t) - 1\)。

所以:\(f_{i,j} = \max(f_{i,j}, f_{t,j - c} + c + 1)\)

因为如果要添加 \(c\) 个点,\(t\) 点只能添加 \(j - c\) 个点,然后加上添加的 \(c\) 个点再加一,就能得到上升点列的长度。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 510;
struct node{
	int x, y;
} a[N];
int n, k, f[N][N];

bool cmp(node n1, node n2) {
	return n1.x < n2.x || (n1.x == n2.x && n1.y < n2.y);
}

int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].x, &a[i].y);
	sort(a + 1, a + n + 1, cmp);
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= k; j++) {
			f[i][j] = j + 1;
		}
	}
	int c;
	for (int i = 2; i <= n; i++) {
		for (int t = 1; t < i; t++) {
			if (a[t].y > a[i].y) continue;
			c = a[i].x - a[t].x + a[i].y - a[t].y - 1;
			for (int j = c; j <= k; j++)
				f[i][j] = max(f[i][j], f[t][j - c] + c + 1);
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) ans = max(ans, f[i][k]);
	printf("%d", ans);
	return 0;
}

标签:P8816,个点,int,添加,n1,n2,CSP,点列
From: https://www.cnblogs.com/yhx0322/p/17739711.html

相关文章

  • P8815 [CSP-J 2022] 逻辑表达式
    Problem考察算法:后缀表达式计算、建表达式树、\(DFS\)。题目简述给你一个中缀表达式,其中只有\(\&\)和\(\mid\)两种运算。求:\(\&\)和\(\mid\)运算中的“最短路”次数各出现了多少次。最短路的定义为:在\(a\)\(\&\)\(b\)运算中,如果\(a=0\),那么整个表达式的计算......
  • P7073 [CSP-J2020] 表达式
    Problem考察算法:后缀表达式建树,优化。题目简述读入一个后缀表达式,由\(\&,\mid,!\)三种运算和操作数构成。有\(q\)次询问,每次输入一个下标\(i\),表示要取反\(x_i\)的值。每次求表达式的值。暴力每次重新建表达式树,计算。时间复杂度:\(O(q\times|s|)\),达到了惊人的\(10......
  • P7072 [CSP-J2020] 直播获奖
    Problem考查知识点:桶优化。题目简述竞赛的获奖率为\(w\%\),即当前排名前\(w\%\)的选手的最低成绩就是即时的分数线。若当前已评出了\(p\)个选手的成绩,则当前计划获奖人数为\(\max(1,\lfloorp\timesw\%\rfloor)\),如有选手成绩相同,则所有成绩并列的选手都能获奖,因此实......
  • P7074 [CSP-J2020] 方格取数
    Problem相关算法:\(DP\)。题意简述给你一个方格图,每次只能向上、向右、向下走。现在求:经过所有点取到的数字和的最大值。思路动态规划。对于每一列而言,如果某个点向上走了,就不可能再向下走。向下走了同理。所以我们可以把两种情况都尝试一遍,每个点而言,如果是处于向下的状态......
  • CSP模拟30
    CSP模拟30难得改完一次题,写篇题解祭一下A.枫(P7485「Stoi2031」枫)考场居然打了个高分暴力我的思路:假设我们已知最后一个数,逆推,不断往该数前(或后)加了多少数,直至完成这个操作。荣获$96pts$的好成绩评测记录代码如下:#include<bits/stdc++.h>usingnamespacestd;constin......
  • CSP2023 游记
    前言:之所以不在标题中加上&这个字符以及后面那几个字,是准备在复赛后加。今年没报J。下文的qbn,yh,lyl,yts。正文:初赛:每次敲code都用g++编译,甚至暑假在jcsy的时候由于配置VC较麻烦,直接手敲命令的,结果选择题第11题还对不了。。。阅读程序最后一题连错两道......
  • CSP-S 2021 廊桥分配 题解
    part1:题目描述:当一架飞机抵达机场时,可以停靠在航站楼旁的廊桥,也可以停靠在位于机场边缘的远机位。乘客一般更期待停靠在廊桥,因为这样省去了坐摆渡车前往航站楼的周折。然而,因为廊桥的数量有限,所以这样的愿望不总是能实现。机场分为国内区和国际区,国内航班飞机只能停靠在国内......
  • 2023 CSP-S 备战
    2023CSP-S备战日常犯智9.29Dinic中,如果rest为\(0\),直接终止循环。intdinic(intu,intflow){ if(u==T)returnflow; intrest=flow; for(inti=now[u];i&&rest;i=edge[i].nxt){//rest now[u]=i; intv=edge[i].v,c=edge[i].c; ......
  • 洛谷 P7075[CSP-S2020] 儒略日
    [CSP-S2020]儒略日题目描述为了简便计算,天文学家们使用儒略日(Julianday)来表达时间。所谓儒略日,其定义为从公元前4713年1月1日正午12点到此后某一时刻间所经过的天数,不满一天者用小数表达。若利用这一天文学历法,则每一个时刻都将被均匀的映射到数轴上,从而得以很方便的......
  • 济南 CSP-S NOIP 储备营笔记
    Day1上午——基础算法模拟+枚举小前言碰到题目不会做->先写个模拟压压惊()枚举法枚举的思想是不断地猜测,从所有可能的集合中一一尝试,然后再判断是否符合题目的条件。单独提到枚举时我们往往认为这是一个暴力做法,但事实上并非如此,恰当的枚举往往会是解题的关键步骤。......