题目：赤壁之战
一个长度为N的序列A，求A有多少个长度为M的严格递增子序列。
输入格式
第一行包含整数T，表示共有T组测试数据。 每组数据，第一行包含两个整数N和M。 第二行包含N个整数，表示完整的序列A。
输出格式
每组数据输出一个结果，每个结果占一行。输出格式为“Case #x: y”，x为数据组别序号，从1开始，y为结果。由于数据可能很大，请你输入对109+7109+7取模后的结果。
数据范围
1≤T≤1001≤T≤100,
1≤M≤N≤10001≤M≤N≤1000,
序列中的整数的绝对值不超过109109。
输入样例：
2
3 2
1 2 3
3 2
3 2 1
输出样例：
Case #1: 3
Case #2: 0
思路：dp[i][j]表示长度为i，当前到 j 个数最长上升序列
状态转移：dp[i][j]+=dp[i][k] {j>k&&a[j]>a[k]}
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define N 1001using namespace std;const long long mod=1000000007;int a[N],dp[N][N],sum;int main(){int t;cin>>t;for(int s=1;s<=t;s++){memset(dp,0,sizeof(dp));int n,m;cin>>n>>m;for(int i=1; i<=n; i++) cin>>a[i];a[0]=-(1<<30);dp[0][0]=1;for(int i=1; i<=m; i++){for(int j=1; j<=n; j++){for(int k=0; k<j; k++){if(a[j]>a[k]) dp[i][j] =(dp[i][j]+dp[i-1][k])%mod;}}}long long ans=0;for(int i=1; i<=n; i++){ans=(ans+dp[m][i])%mod;}printf("Case #%d: %lld\n",s,ans);}}
优化算法：因为每次j增长1，只是k的取值范围只是从1~j 到 1~j+1，所以可以用树状数组储存1到j中的可选值，然后j增长时，增加j+1范围。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define N 1001#define ll long longusing namespace std;const long long mod=1000000007;int a[N],b[N],n,m,dp[N][N],sum,c[N];int lowbit(int x){return x&(-x);}ll ask(int x){ll ans=0;for(;x;x-=lowbit(x)){ans=(ans+c[x])%mod;}return ans;}void add(int x,int val){for(;x<=n;x+=lowbit(x)){c[x]=(c[x]+val)%mod;}}int main(){int t;cin>>t;for(int s=1;s<=t;s++){memset(dp,0,sizeof(dp));cin>>n>>m;for(int i=1; i<=n; i++) {cin>>a[i];b[i]=a[i];}sort(b+1,b+1+n);for(int i=1;i<=n;i++) {a[i]=lower_bound(b+1,b+1+n,a[i])-(b-1);//a[i]为在整个数组中的大小排名}// -----离散化，将a[i]将数字缩小，但仍保持相对大小关系dp[0][0]=1;for(int i=1; i<=m; i++){memset(c,0,sizeof(c));if(i==1) add(1,dp[i-1][0]);for(int j=1; j<=n; j++){dp[i][j]=ask(a[j]-1);add(a[j],dp[i-1][j]);}}long long ans=0;for(int i=1; i<=n; i++){ans=(ans+dp[m][i])%mod;}printf("Case #%d: %lld\n",s,ans);}}
