递推式比较好想 以当前到达的位置和已选定的个数为状态的的d[i][j] = sum(d[k][j+1] ) ;直接dp超时;
可用m个树状数组存储每个d【k】【m】;但插入的位置很重要即要按大小的rank值存入每个点;
还有一点很重要,枚举i,j的顺序 必须先i后j ,是的在计算d【i】【j】时,m+1行只算了比j大的值;
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 10005; const int maxm = 105; long long d[maxm][maxn],a[maxn],lim=10001; long long b[maxm][maxn],rank[maxn]; int MOD=123456789; struct node{ int id,Rank,x; bool operator < (const node& rhs) const{ return x<rhs.x; } }ta[maxn]; int lowbit(int x){return x&-x;} long long sum(int m ,int x){ long long ret=0; while(x>0){ ret+=b[m][x]; x-=lowbit(x); } return ret; } long long query(int m,int l,int r){ return sum(m,r) - sum(m,l-1); } void update(int m,int x,int d){ while(x <= lim){ b[m][x] +=d; x+=lowbit(x); } } int n,m; int main() { while(scanf("%d %d",&n,&m)==2){ for(int i=1;i<=n;i++){ scanf("%I64d",&a[i]); ta[i].x=a[i]; ta[i].id=i; } memset(b,0,sizeof(b)); sort(ta+1,ta+1+n); int key=1; for(int i=1;i<=n;i++){ if(i!=1&&ta[i-1].x!=ta[i].x) ++key; rank[ta[i].id] = key+1; } rank[0]=1; for(int j=n;j>=0;j--) for(int i=m;i>=0;i--){ { if(i==m) {d[i][j] = 1; update(i,rank[j],d[i][j]); continue;} if(j==n) {d[i][j] = 0; update(i,rank[j],d[i][j]); continue;} d[i][j]=0; d[i][j]=query(i+1,rank[j]+1,lim)%MOD; update(i,rank[j],d[i][j]); } } printf("%I64d\n",d[0][0]); } return 0; }