题意
这题题意很直白,这里不再解释。
算法
一旦发现有道题看着比较玄乎,很难用正常算法求,那八成就是 DP。
状态设计很容易想到。设 $dp_{i,j}$ 为以 $i$ 结尾且长度为 $j$ 的单调上升子序列用多少个,那么状态转移方程就是:
$$ dp_{i,j}= \begin{cases} 1&\text{if } j=1\\\ \sum\limits_{1\le k\lt i \text{ 且 } A_k\lt A_i} dp_{k,j-1}&\text{else} \end{cases} $$
这样时间复杂度为 $O(TN^2M)$,$10^2\*{10^3}^2\*{10^3}=10^{11}$ 妥妥爆炸。
所以,就要用到数据结构去优化了。
数据结构优化 DP,最主要用到线段树、树状数组和平衡树,这题就可以用一个二维树状数组来做。
二维树状数组第一维用来满足查询操作,第二维满足转移方程中 $A_k\lt A_i$。至于 $1\le k\lt i$,逐行添加即可。
但是 $A_i$ 值太大,无法直接作为下标,需要进行离散化,映射到 $N$ 以内才行。具体见代码。
代码
代码里有注释
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const ll P = 1000000007;
int T;
int N;
int M;
int A[1009];
int b[1009];
int cnt;
ll dp[1009][1009]; //开 long long 保险一些
ll tr[1009][1009];
ll res;
int LowBit (int x) {
return x & -x;
}
void Modify (int x, int p, ll v) { //两维,第一维是当前为第几列,第二位是 A[i]
for (int i = p; i <= cnt; i += LowBit(i)) {
tr[x][i] = (tr[x][i] + v) % P;
}
}
ll Query (int x, int p) {
ll ans = 0;
for (int i = p; i; i -= LowBit(i)) {
ans = (ans + tr[x][i]) % P;
}
return ans;
}
void In_Solve_Out () {
int c = 0;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &N, &M);
for (int i = 1; i <= N; i++) {
scanf("%d", &A[i]);
b[i] = A[i];
}
sort(b + 1, b + N + 1);
cnt = unique(b + 1, b + N + 1) - b - 1; //离散化
for (int i = 1; i <= N; i++) {
A[i] = lower_bound(b + 1, b + cnt + 1, A[i]) - b + 1;
}
memset(dp, 0, sizeof(dp)); memset(tr, 0, sizeof(tr));
res = 0;
for (int i = 1; i <= N; i++) {
dp[i][1] = 1;
}
for (int i = 1; i <= N; i++) {
for (int m = 2; m <= min(i, M); m++) { //m>i 没有意义,非法状态,不计算
dp[i][m] = (dp[i][m] + Query(m - 1, A[i] - 1)) % P; //必须单调递增,所以是 A[i]-1
}
res = (res + dp[i][M]) % P;
for (int m = 1; m <= min(i, M); m++) {
Modify(m, A[i], dp[i][m]);
}
}
c++;
printf("Case #%d: %d\n", c, res);
}
}
int main () {
In_Solve_Out();
return 0;
}