UVA12983 The Battle of Chibi 题解

第一眼能看出来是个dp

O( n 3 n^3 n3) 暴力应该很好想 dp[i][j] = ∑ k = 1 i [ a [ k ] < a [ i ] ] ∗ d p [ k ] [ j − 1 ] \sum_{k=1}^i [a[k] < a[i]] *dp[k][j-1] ∑k=1i​[a[k]<a[i]]∗dp[k][j−1]

发现dp[i][j] 为前面小于它的数长度为j-1的总和, 用树状数组前缀和优化一下搞成 O ( n 2 l o g n ) O(n^2log_n) O(n2logn​)

先离散化, dp时先枚举位置,再枚举上升序列的长度

树状数组要开二维哦, 打代码的时候发现dp数组可以用树状数组直接代替(小小的空间优化)

代码:

#include
#include
#include
#include
using namespace std;
const int N = 1005;
const int P = 1e9+7;
int read(void) {int x = 0;char c = getchar();while (!isdigit(c)) c = getchar();while (isdigit(c)) {x = (x << 3) + (x << 1) + c - '0';c = getchar();}return x;
}
int T, n, m;
int a[N];
struct node{int pos, val;bool operator < (const node &i) const {if (val == i.val) return pos < i.pos;return val < i.val;}
}p[N];
bool cmp(node i,node j) {return i.pos < j.pos;
}
long long d[N][N];
inline int low(int x) {return x & -x;
}
int sum(int x,int p) {long long val = 0;for (;x;x -= low(x)) val += d[p][x];return val % P;
}
void add(int x,int k,int p) {for (;x <= n; x += low(x)) d[p][x] = (d[p][x] + k) % P;
}
int main() {T = read();int cnt = 0;while (T--) {cnt++;n = read(), m = read();for (int i = 1;i <= n; i++) p[i] = (node){i,read()};sort(p + 1,p + n + 1);int x = 0, k = 0;for (int i = 1;i <= n; i++) {if (x == p[i].val) p[i].val = k;else {x = p[i].val;p[i].val = i;k = i;}}sort(p + 1,p + n + 1, cmp);memset(d, 0, sizeof(d));long long ans = 0;for (int i = 1;i <= n; i++) {add(p[i].val, 1, 1);for (int j = 2;j <= m; j++) {int k = sum(p[i].val-1, j-1);add(p[i].val, k, j);if (j == m) ans = (ans + k) % P;}}if (m == 1) ans += n;printf ("Case #%d: %lld\n", cnt, ans % P);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！