Removing Robots题解

maple_trees_112 · 2023-10-07 21:53:11 · 题解

一眼望去，就是一个 dp，我笑了笑，就开始写方程式

我们假设 dp_{i,0} 表示的是后 i 个的方案数，由此我们可以得出以下的状态转移方程。

所以我们得把 dp_{n + 1} 初始化。

然后这里需要用单调队列来维护，这个应该相对简单一点。

还有啊，记得取模啊。

#include<bits/stdc++.h>
const int maxn = 200005,p = 998244353;
using namespace std;
int n,dp[maxn];
std::pair <int,int> a[maxn];
std::stack < pair<int,int> > gf;
int main() 
{
    std::cin>>n;
    for(int i = 1;i <= n;i++) 
    {
        std::cin>>a[i].first>>a[i].second;
    }
    std::sort(a + 1,a + 1 + n);
    dp[n + 1] = 1;
    for(int i = n;i >= 1; i--) 
    {
        int t = a[i].first + a[i].second, next = i + 1;
        while(!gf.empty() && t > a[gf.top().first].first) 
        {
            next = gf.top().second;
            gf.pop();
        }
        gf.push({i, next});
        dp[i] = (dp[i+1] + dp[next]) % p;
    }
    std::cout<<dp[1];
}

完结撒花.