题目链接
http://codeforces.com/problemset/problem/597/C
题意
给出一个n 一个 k
求 n 个数中 长度为k的上升子序列 有多少个
思路
刚开始就是想用dp 复杂度 大概是 O(n ^ 2 * k)
T了
但是 思路还是一样的 只是用树状数组 优化了一下 第三层循环
dp[i][j] 表示 第 i 个数 长度为 j 时
那么 dp[i][j] 的状态转移就是 ∑(arr[i] > arr[k] ? : dp[k][j - 1] )
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)); #define pb push_back #define bug puts("***bug***"); #define X first #define Y second #define L(on) (on<<1) #define R(on) (L(on) | 1) #define all(x) x.begin(), x.end() #define stack_expand #pragma comment(linker, "/STACK:102400000,102400000") #define syn_close ios::sync_with_stdio(false);cin.tie(0); //#define bug //#define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <string, int> psi; typedef pair <string, string> pss; typedef pair <double, int> pdi; const double PI = acos(-1.0); const double EI = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int maxn = 1e5 + 10; const int MOD = 6; int arr[maxn]; ll dp[maxn][15]; int lowbit(int x) { return x & (-x); } ll sum(int x, int y) { ll ans = 0; while (x > 0) { ans += dp[x][y]; x -= lowbit(x); } return ans; } void add(int x, int y, ll val) { while (x <= maxn) { dp[x][y] += val; x += lowbit(x); } } int main() { int n, m; scanf("%d%d", &n, &m); m++; for (int i = 1; i <= n; i++) scanf("%d", &arr[i]); CLR(dp, 0); for (int i = 1; i <= n; i++) { for (int j = 1; j <= min(i + 1, m); j++) { if (j == 1) add(arr[i], 1, 1); else { ll temp = sum(arr[i] - 1, j - 1); add(arr[i], j, temp); } } } printf("%lld\n", sum(n, m)); } //int arr[maxn]; // origin idea TLE on test 19 // //ll dp[maxn][15]; // //int main() //{ // int n, K; // scanf("%d%d", &n, &K); // K++; // for (int i = 0; i < n; i++) // scanf("%d", &arr[i]); // CLR(dp, 0); // for (int i = 0; i < n; i++) // dp[i][1] = 1; // for (int i = 1; i < n; i++) // { // for (int j = 2; j <= min(i + 1, K); j++) // { // for (int k = 0; k < i; k++) // { // if (arr[i] > arr[k]) // dp[i][j] += dp[k][j - 1]; // } // } // } // ll ans = 0; // // for (int i = 0; i < n; i++) // ans += dp[i][K]; // // cout << ans << endl; //}转载于:https://www.cnblogs.com/Dup4/p/9433072.html
相关资源：JAVA上百实例源码以及开源项目