以纵坐标为编号建树状数组优化动态规划
#include<algorithm> #include<iostream> #include<cstdio> #define mod 100007 using namespace std; struct point{ int x,y; }p[100001]; int n,K,f[100001][16][2],a[16][2][100001],ans; inline bool cmp(point x,point y){ return x.x<y.x; } inline void add(int x,int v,int j,int k){ for(int i=x;i<=100000;i+=(i&(-i))) a[j][k][i]=(a[j][k][i]+v)%mod; } inline int que(int x,int j,int k){ int sum=0; for(int i=x;i;i-=(i&(-i))) sum=(sum+a[j][k][i])%mod; return sum; } int main(){ //freopen("line.in","r",stdin); //freopen("line.out","w",stdout); scanf("%d%d",&n,&K); for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y); sort(p+1,p+n+1,cmp); for(int i=1;i<=n;i++){ f[i][0][0]=f[i][0][1]=1; add(p[i].y,1,0,0);add(p[i].y,1,0,1); for(int j=1;j<=K;j++){ f[i][j][0]+=que(p[i].y-1,j,0)+que(p[i].y-1,j-1,1); f[i][j][1]+=que(100000,j,1)-que(p[i].y,j,1)+que(100000,j-1,0)-que(p[i].y,j-1,0); f[i][j][0]%=mod;f[i][j][1]%=mod; if(f[i][j][1]<0)f[i][j][1]+=mod; add(p[i].y,f[i][j][0],j,0);add(p[i].y,f[i][j][1],j,1); } } for(int i=1;i<=n;i++){ ans=(ans+f[i][K][0])%mod; ans=(ans+f[i][K][1])%mod; } printf("%d\n",ans); return 0; }