数据结构优化DP
例题A题解
设 \(f_{i,j}\) 表示以第 \(i\) 位为结尾,长度为 \(j\) 的严格单调上升子序列的数量。
那么显然有 \(f_{i,j}=\sum_{k=1}^{i-1}f_{k,j-1}\times(a_k<a_i)\)
然后发现这玩应 \(O(n^2m)\) 直接寄掉了。
考虑优化。
发现只有当 \(a_k<a_i\) 时才会有贡献。
于是离散化+权值BIT就完事了。
例题A代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f= -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 1e5 + 10, mod = 123456789;
int n, a[maxn], m;
vector<int> vec;
struct BIT{
int c[maxn];
inline int lowbit(int x){return x & (-x);}
void upd(int x,int upd){for(;x <= n;x += lowbit(x))c[x] = (c[x] + upd) % mod;}
int qry(int x){int ans = 0;for(;x;x -= lowbit(x))ans = (ans + c[x]) % mod;return ans;}
void clear(){for(int i = 0;i <= n;i++)c[i] = 0;}
}tree[101];
signed main(){
while(scanf("%lld%lld",&n,&m) != EOF){
for(int i = 1;i <= n;i++){vec.push_back(a[i] = read());}
sort(vec.begin(),vec.end());vec.erase(unique(vec.begin(),vec.end()),vec.end());
int ans = 0;
for(int i = 1;i <= n;i++){
int x = lower_bound(vec.begin(),vec.end(),a[i]) - vec.begin() + 1;
tree[1].upd(x,1);
for(int j = 1;j <= m;j++)
tree[j].upd(x,tree[j - 1].qry(x - 1));
}
ans = tree[m].qry(n);
printf("%lld\n",ans);
for(int i = 1;i <= m;i++)tree[i].clear();vec.clear();
}
return 0;
}