题意: 给长度为 n 的数组, 问有多少长度为 m 单调递增子序列? n,m<=1000
思路: 设 f[i][j] 表示长度为 i 的以 aj 为结尾的单调递增子序列的方案数, 易得 f[i][j]=f[i][j]+f[i-1][k] (ak<aj)
第一层枚举 n, 第二层枚举 m, 第三层枚举小于 m 的位置, 其中第一层, 第二层由于状态方程是无法改变的, 而第三层枚举小于 m 的位置的所有小于 a[j] 的值都是要计算的, 所以可以使用树状数组, 以 a[j] 作为下标, f[i][j] 为对应的值, 这样每一层来说统计上一层中小于 a[j] 的个数, 就是树状数组中的前缀和了, 然后到了下一层在更新树状数组就可以.
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- const int maxn=1e3+10;
- const int mod=1e9+7;
- ll c[maxn];
- struct note
- {
- int id,val;
- } a[maxn];
- int pos[maxn];
- int f[1005][1005];
- int cmp(note a,note b)
- {
- return a.val<b.val;
- }
- int n,m;
- ll ask(int x)
- {
- ll ans=0;
- for(; x; x-=x&-x)
- ans+=c[x];
- return ans;
- }
- void add(int x,int y)
- {
- for(; x<=n; x+=x&-x) c[x]+=y;
- }
- int main()
- {
- int T;
- scanf("%d",&T);
- for(int it=1;it<=T;it++)
- {
- scanf("%d%d",&n,&m);
- for(int i=1; i<=n; i++)
- {
- scanf("%d",&a[i].val);
- a[i].id=i;
- }
- sort(a+1,a+1+n,cmp);
- for(int i=1; i<=n; i++)
- pos[a[i].id]=i;
- memset(f,0,sizeof(f));
- memset(c,0,sizeof(c));
- for(int i=1; i<=n; i++)
- f[1][i]=1;
- for(int i=2; i<=m; i++)
- {
- for(int j=1; j<=n; j++)
- {
- f[i][j]=(f[i][j]+ask(pos[j]-1))%mod; // 开始计算 i 层 求小于 a[i] 的方案数.
- add(pos[j],f[i-1][j]); // 更新为上一层 i-1 的方案数
- }
- memset(c,0,sizeof(c)); // 清空
- }
- ll ans=0;
- for(int i=1; i<=n; i++)
- ans=(ans+f[m][i])%mod;
- printf("Case #%d: %lld\n",it,ans);
- }
- }
- View Code
来源: http://www.bubuko.com/infodetail-3229858.html