[BZOJ4621]Tc605

試題描述

最初你有一個長度為 \(N\) 的數字序列 \(A\)。為了友善起見，序列 \(A\) 是一個排列。

你可以操作最多 \(K\) 次。每一次操作你可以先標明一個 \(A\) 的一個子串，然後将這個子串的數字全部變成原來這個子串的最大值。問最終有幾種可能的數字序列。答案對 \(10^9+7\) 取模。

輸入

第一行兩個數 \(N\) 和 \(K\)。第二行 \(N\) 個數，描述一個排列 \(A\)。

輸出

輸出一個數，表示答案在模域下的值。

輸入示例

3 2
3 1 2                

輸出示例

資料規模及約定

\(N,K \le 500\)，有 \(6\) 組資料 \(N>100\)，有梯度

題解

令 \(f(i, j)\) 表示前 \(i\) 個位置操作了 \(j\) 次的可能序列數。

但是直接轉移非常困難，我們從第 \(1\) 個數開始依次把這個 dp 值用刷表法得出來。假設第 \(i\) 個數能覆寫到區間 \([l, r]\)，那麼 \([l, r]\) 的任意子區間都可以是這個數且隻有這個子區間是這個數。這樣我們就可以對于 \(k \in [l, r]\)，\(f(k, j)\) 的值就會增加 \(\sum_{t=l-1}^{k-1} f(t, j-1)\)，我們順序掃這個 \(k\) 同時維護字首和就可以了。注意如果在某個轉移中 \(i\) 隻影響到 \([i, i]\) 這個區間，不能算作“一步”，即 \(f(i-1, j)\) 能直接轉移到 \(f(i, j)\)，而不是 \(f(i-1, j-1)\) 轉移到 \(f(i, j)\)。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define rep(i, s, t) for(int i = (s), mi = (t); i <= mi; i++)
#define dwn(i, s, t) for(int i = (s), mi = (t); i >= mi; i--)

int read() {
    int x = 0, f = 1; char c = getchar();
    while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
    while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

#define maxn 510
#define MOD 1000000007
#define LL long long

int n, K, A[maxn], f[maxn][maxn];

int main() {
    n = read(); K = read();
    rep(i, 1, n) A[i] = read();
    
    f[0][0] = 1;
    rep(i, 1, n) {
        int l = i, r = i;
        while(l > 1 && A[l-1] <= A[i]) l--;
        while(r < n && A[r+1] <= A[i]) r++;
        dwn(j, K, 1) {
            f[i][j] += f[i-1][j]; if(f[i][j] >= MOD) f[i][j] -= MOD;
            int sum = 0;
            rep(k, l, r) {
                sum += f[k-1][j-1]; if(sum >= MOD) sum -= MOD;
                f[k][j] += sum; if(f[k][j] >= MOD) f[k][j] -= MOD;
            }
            f[i][j] -= f[i-1][j-1]; if(f[i][j] < 0) f[i][j] += MOD;
        }
        f[i][0] += f[i-1][0]; if(f[i][0] >= MOD) f[i][0] -= MOD;
    }
    
    int ans = 0;
    rep(i, 0, K) {
        ans += f[n][i];
        if(ans >= MOD) ans -= MOD;
    }
    printf("%d\n", ans);
    
    return 0;
}                

轉載于:https://www.cnblogs.com/xiao-ju-ruo-xjr/p/8490708.html