前言:
hard,看题解才知道逆推。。。
有没有正推的做法呢,很想知道正推是怎么做的。
题意:
给定k条线段,一共有n个时刻,同一时刻只能有一条线段覆盖。
问最多有多少个点不能被覆盖到。
做法:
f[i]表示从i开始到n最多有多少个点没有覆盖。
然后逆着dp就很显然了。
int f[N];
struct node
{
int l, r;
};
vector<node> v[N];
void solve()
{
int n, k;
cin >> n >> k;
for (int i = 1; i <= k; i++)
{
int p, t;
cin >> p >> t;
v[p].push_back({p, p + t - 1});
}
for (int i = n; i >= 1; i--)
{
if (v[i].empty()) f[i] = f[i + 1] + 1;
else
{
for (auto j : v[i])
{
f[i] = max(f[i], f[j.r + 1]);
}
}
}
cout << f[1];
}