思维dp ---- 复杂状态找中间状态作为dp状态 1552F - Telepanting

题目链接

---

题目大意：

有个蚂蚁从 0 0 0号点要到 x n + 1 x_n+1 xn​+1的位置。
在 x 0 , x 1 , x 2 , x 3 , . . . . . , x n + 1 , x n x_0,x_1,x_2,x_3,.....,x_{n+1},x_n x0​,x1​,x2​,x3​,.....,xn+1​,xn​的传送阵，每个 x i x_i xi​传送阵可以把你传送回 y i ( y i < x i ) y_i(y_i<x_i) yi​(yi​<xi​)位置。但是每个传送阵有两种转态

1. 0 : 0: 0:这个传送阵无法传送，但是你经过它会变成状态 1 1 1
2. 1 : 1: 1:这个传送阵正常工作，工作完之后变成状态 0 0 0

问你需要多少时间走到 x n + 1 x_n+1 xn​+1

---

解题思路：

1. 首先我们当前在 p o s pos pos位置，那么所有 x i < p o s x_i<pos xi​<pos的传送阵状态都变成了 1 1 1
2. 现在我们现在设 d p [ i ] dp[i] dp[i]为假设第 i i i个传送阵为 1 1 1,并且再次回到位置 i i i的时间！
3. 那么转移就很明显了 d p [ i ] = ∑ k = i d x i − 1 d p [ k ] dp[i]=\sum_{k=idx}^{i-1}dp[k] dp[i]=∑k=idxi−1​dp[k]
4. i d x 是 第 一 个 位 置 ≤ y i 的 传 送 阵 位 置 idx是第一个位置\leq y_i的传送阵位置 idx是第一个位置≤yi​的传送阵位置
5. 最终答案就是 a n s = x n + 1 + ∑ i = 1 n d p [ i ] × [ s t a t e [ i ] = = 1 ] ans=x_n+1+\sum_{i=1}^{n}dp[i]\times[state[i]==1] ans=xn​+1+∑i=1n​dp[i]×[state[i]==1]

---

AC代码：

#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define Lson rt << 1, l , mid
#define Rson rt << 1|1, mid + 1, r
#define ms(a,al) memset(a,al,sizeof(a))
#define log2(a) log(a)/log(2)
#define lowbit(x) ((-x) & x)
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INF 0x3f3f3f3f
#define LLF 0x3f3f3f3f3f3f3f3f
#define f first
#define s second
#define endl '\n'
using namespace std;
const int N = 2e6 + 10, mod = 998244353;
const int maxn = 500010;
const long double eps = 1e-5;
const int EPS = 500 * 500;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<double,double> PDD;
template<typename T> void read(T &x)
{
   x = 0;char ch = getchar();ll f = 1;
   while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
   while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) 
{
   read(first);
   read(args...);
}
int n;
int x[maxn], state[maxn];
ll sum[maxn], q[maxn];
int main() {
    IOS;
    cin >> n;
    for(int i = 1; i <= n; ++ i) {
       int y;
       cin >> x[i] >> y >> state[i];
       int j = lower_bound(x+1,x+i+1,y)-x;
       q[i] = ((sum[i-1] - sum[j-1] + mod) % mod + x[i] - y) % mod;
       sum[i] = (sum[i-1] + q[i]) % mod;
    }
    ll ans = 0;
    for(int i = 1; i <= n; ++ i) 
       if(state[i]) {
          ans = (ans + q[i]) % mod;
       }
    cout << (ans + x[n] + 1) % mod;
    return 0;
}