codeforces D. Array Collapse

2023-12-20 20:52:53

DP一生之敌
learn from AC-Panda and codeforces’s Tutorial

思路

  • d p [ i ] dp[i] dp[i] 表示以 a [ i ] a[i] a[i] 结尾的方案数, s u m [ i ] sum[i] sum[i] 表示 ∑ j = 1 i d p j \sum\limits_{j=1}^idp_j j=1i?dpj?
  • 对于 d p [ i ] dp[i] dp[i] D P DP DP a [ i ] a[i] a[i] 后面的数我们思考 d p [ i ] dp[i] dp[i] 是否存在。
    • a [ j ] > a [ i ] a[j] > a[i] a[j]>a[i] ,显然可以包含 c o n t i g u o u s ?? s u b s e g m e n t [ j , n ] contiguous\;subsegment [j,n] contiguoussubsegment[j,n] 保证 d p [ i ] dp[i] dp[i] 存在。
    • a [ j ] < a [ i ] a[j] < a[i] a[j]<a[i] ,根据题意显然无法做到保留 a [ i ] a[i] a[i] 且不保留 a [ j ] a[j] a[j] ,此时 d p [ i ] dp[i] dp[i] 不存在。
    • 无法保留但可以替换,就是说对于 d p [ i ] dp[i] dp[i] 我们可以根据题意将其末尾的 a [ i ] a[i] a[i] 替换为 a [ j ] a[j] a[j]
    • i < k < j i< k <j i<k<j a [ i ] a[i] a[i] 是从右往左第一个比 a [ j ] a[j] a[j] 小的数,那么所有的 d p [ k ] dp[k] dp[k] 的末尾都可以被 a [ j ] a[j] a[j] 替换。
    • a [ j ] a[j] a[j] 当然还可以拼接在所有合理方案的后面。
  • 用单调栈维护从右往左第一个小的数。
  • 单调栈时也要维护 a n s ans ans ,就是减去不存在的。

Think Twice, Code Once

#include <bits/stdc++.h>
#define il inline
#define get getchar
#define put putchar
#define is isdigit
#define int long long
#define dfor(i,a,b) for(int i=a;i<=b;++i)
#define dforr(i,a,b) for(int i=a;i>=b;--i)
#define dforn(i,a,b) for(int i=a;i<=b;++i,put(10))
#define mem(a,b) memset(a,b,sizeof a)
#define memc(a,b) memcpy(a,b,sizeof a)
#define pr 114514191981
#define gg(a) cout<<a,put(32)
#define INF 0x7fffffff
#define tt(x) cout<<x<<'\n'
#define endl '\n'
#define ls i<<1
#define rs i<<1|1
#define la(r) tr[r].ch[0]
#define ra(r) tr[r].ch[1]
#define lowbit(x) (x&-x)
#define ct cin.tie(nullptr),ios_base::sync_with_stdio(false)
using namespace std;
typedef unsigned int ull;
typedef pair<int, int> pii;
int read(void) {
    int x=0,f=1;char c=get();
    while(!is(c)) (f=c==45?-1:1),c=get();
    while(is(c)) x=(x<<1)+(x<<3)+(c^48),c=get();
    return x*f;
}
void write(int x) {
    if (x < 0) x = -x, put(45);
    if (x > 9) write(x / 10);
    put((x % 10) ^ 48);
}
#define writeln(a) write(a), put(10)
#define writesp(a) write(a), put(32)
#define writessp(a) put(32), write(a)
const int N = 2e5 + 10, M = 1e5 + 10, SN = 1e3 + 10, mod = 998244353;
signed main() {
    int T = 1;
    T = read();
    while (T--) {
        int n = read();
        vector<int> a(n + 1), dp(n + 1), sum(n + 1);
        for (int i = 1; i <= n; ++i) a[i] = read();
        stack<int> sta;
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            int cnt = 0;
            while (!sta.empty() && a[i] < a[sta.top()]) ans -= dp[sta.top()], sta.pop();
            if (sta.empty()) dp[i] = (sum[i - 1] + 1) % mod;
            else dp[i] = (sum[i - 1] - sum[sta.top()] + ans) % mod;
            sum[i] = (sum[i - 1] + dp[i]) % mod;
            ans = (ans + dp[i]) % mod;
            sta.push(i);
        }
//        for (int i = 1; i <= n; ++i) writesp(dp[i]);
//        puts("");
        writeln((ans + mod) % mod);
    }
    return 0;
}

文章来源:https://blog.csdn.net/wyzz_yz/article/details/135111714
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。