The Battle of Chibi(树状数组优化DP)

题目链接：
https://vjudge.net/contest/390155#problem/M
题目大意：
给你一个长度为n的数组，问你这个数组中有多少种长度为m的递增序列，输出种类数。
思路：
这道题的状态转移方程很好想，我们用$dp[i][j]$表示以第$j$位的数结尾，递增序列长度为$i$的种类数。
那么转移方程就可以写成：
$$dp[i][j]=dp[i][j]+dp[i-1][k],(a[k]<a[j])$$

/** @沉着，冷静！: 噗，这你都信！* @LastEditors: HANGNAG* @LastEditTime: 2020-09-16 17:21:16* @FilePath: \ACM_vscode\DP\DP.cpp*/
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define emplace_back push_back
#define pb push_back
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int N = 1e3 + 10;
int dp[N][N];
int a[N];
int main()
{int t;scanf("%d", &t);int tot = 1;while (t--){int n, m;memset(dp, 0, sizeof(dp));scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++){dp[i][1] = 1;}for (int i = 1; i <= n; i++){scanf("%d", &a[i]);}for (int i = 2; i <= n; i++){for (int j = 2; j <= i; j++){for (int k = 1; k < i; k++){if (a[i] > a[k]){dp[i][j] += dp[k][j - 1];}dp[i][j] %= mod;}}}int ans = 0;for (int i = m; i <= n; i++){ans += dp[i][m];//printf("%d %d %d**\n", i, m, dp[i][m]);}ans %= mod;printf("Case #%d: %d\n", tot++, ans);}return 0;
}

很显然这种朴素的写法的复杂度是 O ( n 3 ) O(n^3) O(n3)这道题过不了。
但是我们可以发现它每次加的都是比当前小的数的状态，那么我们可以把这个数组每个数的前缀记录，每次加上它的前缀。（如果现在判断到第j个数，那么我们先找到a[j]排第几个，假设排b[j]，这里的前缀是指把这个数组排序后，dp[i][j]就加上数组里到b[j]-1的前缀和）
这里我们要想实现对一个数组进行修改和前缀查询，可以用线段树和树状数组实现，（树状数组更简单一些）。因为这里a数组范围比较大，但是数量不多，所以我们可以离散化一下a数组。
AC代码：

/** @沉着，冷静！: 噗，这你都信！* @LastEditors: HANGNAG* @LastEditTime: 2020-09-16 21:09:20* @FilePath: \ACM_vscode\DP\DP.cpp*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define emplace_back push_back
#define pb push_back
using namespace std;
typedef long long LL;
const LL mod = 1e9 + 7;
const double eps = 1e-6;
const LL inf = 0x3f3f3f3f;
const LL N = 1e3 + 10;
LL dp[N][N];
LL a[N], b[N], c[N];
LL n, m;
LL lowbit(LL x)
{return x & (-x);
}
LL sum(LL x)
{LL num = 0;while(x){num += c[x];num %= mod;x -= lowbit(x);}return num;
}
void add(LL x,LL y)
{while(x<=n){c[x] += y;c[x] %= mod;x+=lowbit(x);}
}
int main()
{LL t;scanf("%lld", &t);LL tot = 1;while(t--){memset(dp, 0, sizeof(dp));scanf("%lld%lld", &n, &m);for (LL i = 1; i <=n;i++){scanf("%lld", &a[i]);b[i] = a[i];}sort(a + 1, a + 1 + n);for (LL i = 1; i <= n;i++){b[i] = lower_bound(a + 1, a + 1 + n, b[i]) - a+1;}dp[0][0] = 1;for (LL i = 1; i <= m;i++){memset(c, 0, sizeof(c));add(1, dp[i - 1][0]);for (LL j = 1; j <= n;j++){dp[i][j] = sum(b[j]-1);add(b[j], dp[i-1][j]);}}LL ans = 0;for (LL i = 1; i <= n;i++){ans += dp[m][i];ans %= mod;}printf("Case #%lld: %lld\n",tot++, ans);}return 0;
}

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