[BZOJ4621]Tc605
试题描述
最初你有一个长度为 \(N\) 的数字序列 \(A\)。为了方便起见，序列 \(A\) 是一个排列。
你可以操作最多 \(K\) 次。每一次操作你可以先选定一个 \(A\) 的一个子串，然后将这个子串的数字全部变成原来这个子串的最大值。问最终有几种可能的数字序列。答案对 \(10^9+7\) 取模。
输入
第一行两个数 \(N\) 和 \(K\)。第二行 \(N\) 个数，描述一个排列 \(A\)。
输出
输出一个数，表示答案在模域下的值。
输入示例
3 2
3 1 2输出示例
4数据规模及约定
\(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;
}