53 lines
2.3 KiB
C++
53 lines
2.3 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
|
||
const int mod = 1e9 + 7; //取模
|
||
const int N = 1010;
|
||
const int M = 1010;
|
||
|
||
int n; //原序列长度
|
||
int m; //目标序列长度
|
||
int f[N][M];
|
||
int a[N];
|
||
|
||
// 原题链接 https://www.luogu.com.cn/problem/solution/UVA12983
|
||
int main() {
|
||
//加快读入
|
||
cin.tie(0), ios::sync_with_stdio(false);
|
||
|
||
//文件输入
|
||
freopen("UVA12983.in", "r", stdin);
|
||
|
||
//文件输出
|
||
// freopen("UVA12983.out", "w", stdout);
|
||
|
||
int T;
|
||
//测试数据组数
|
||
cin >> T;
|
||
|
||
for (int Case = 1; Case <= T; Case++) { // while(T--) ，由于要输出 Case +数字，所以写成for,为了怕占用i,j变量，起名为idx
|
||
cin >> n >> m; //由n个数字中挑选，最终严格上升子序列的个数为m 个
|
||
int sum = 0; //结果为累加和,因为最终长度为m,可以从m,m+1,m+2,...,n个数字中选择，最终长度为m即可
|
||
|
||
// DP初始化
|
||
memset(f, 0, sizeof(f)); // f[i][j]表示 在前i个数字中选择，并且，是后一位是i的，并且长度是j的 子序列 个数
|
||
//个数的初始值
|
||
|
||
//这个初始值有意思：不管给我几个数字，最终生成的是位的子序列，那么，只有一种可能
|
||
for (int i = 1; i <= n; i++) f[i][1] = 1;
|
||
|
||
for (int i = 1; i <= n; i++) cin >> a[i]; //读入原序列
|
||
|
||
//开始O(N^3)级的DP
|
||
//小的数量在外层循环，大的数量在内层循环，这会影响很大的运算速率
|
||
for (int j = 2; j <= m; j++) // 小数在外层循环;j=1的已经根据实际意义给上了初始值1，从2开始递推
|
||
for (int i = j; i <= n; i++) // 大数在内层循环
|
||
for (int k = 1; k < i; k++) // 遍历所有前序可能
|
||
if (a[k] < a[i]) // 保证严格递增
|
||
f[i][j] = (f[k][j - 1] + f[i][j]) % mod; // 不断累加，不断取模
|
||
|
||
for (int i = m; i <= n; i++) sum += f[i][m]; //在m确定的情况下，每个一个m~n之间的原始长度都包含解
|
||
cout << "Case #" << Case << ": " << sum << endl;
|
||
}
|
||
return 0;
|
||
} |