F. Feed Cats
题意:
在这个有趣的游戏中,您需要喂养来来往往的猫咪。游戏的关卡由 $n$ 步组成。有 $m$ 只猫; $i$ 只猫出现在 $l_{i}$到$r_{i}$(包括$r_{i}$)。在每一步中,您可以喂养当前出现的所有猫咪,或者什么也不做。
如果您喂同一只猫超过一次,它就会暴饮暴食,您就会立即输掉游戏。您的目标是在不导致任何一只猫暴食的情况下喂食尽可能多的猫。
找出您能喂养的最大猫咪数量。
从形式上看,您需要从 $1$ 到$n$ 的线段中选择几个整数点,使得在给定的线段中,没有一个线段覆盖两个或两个以上所选的点,并且有尽可能多的线段覆盖到点。
思路:
考虑DP:
设$dp(i)$ 表示喂点$i$处的猫,并保证是合法的。即点$i$处的猫都是第一次喂。
状态转移:
$dp[i]$ = $\max(dp[1->(j - 1)])$ + 点$i$处猫的数量,其中$j$是点$i$处的所有猫中,最小的左端点
解释:首先,如果一个区间包含了两个区间,比如$[1,5]$, $[1,2]$, $[4,5]$ 这三个区间,分别是三只猫的活动区间,我们只能选择喂两只猫,因为后两个区间里都有第一个区间,如果选择后两个的话,那么第一只猫就会喂死。对于状态的转移,我们肯定是想在点$i$处喂在此出现的所有的猫,并且保证它们不会死。那么我们就需要求出最小的左端点,原因是,从最小的左端点向$i$靠近时,点$i$处的猫会逐渐出现,以至于到点$i$处,所有的猫都出现了,那么对于最小左端点$-1$ 的这个点,在点$i$处的猫一定都没有出现,这样就不曾喂过它们,也就保证了状态的合法性。
设最小的左端点为$j$。只需要求出$1$~$(j-1)$ 中的喂养猫的数量的最大值即可。
点$i$处的猫。我们可以使用差分来记录每个点猫的数量
答案就是max($dp(i)$(1<=$i$<=$n$))
code:
#include <bits/stdc++.h>
using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<int> b(n + 10);
std::vector<int> dp(n + 10);
std::vector<std::vector<int>> a(n + 10);
for (int i = 1; i <= m; i ++) {
int x, y;
std::cin >> x >> y;
b[x] ++,b[y + 1] --;
a[y].push_back(x);
}
for (int i = 1; i <= n + 5; i ++) {
b[i] += b[i - 1];
}
std::vector<int> min(n + 10);
min[n + 1] = 1e9;
for (int i = n; i >= 1; i --) {
min[i] = std::min(min[i + 1],i);
for (auto x : a[i]) {
min[i] = std::min(min[i],x);
}
}
std::vector<int> g(n + 10);
for (int i = 1; i <= n; i ++) {
dp[i] = g[min[i] - 1] + b[i];
g[i] = std::max(g[i - 1],dp[i]);
}
std::cout << g[n] << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}