dp……
令b[i][j]表示n=i,k=j时的答案；
则b[1][0]=1;b[2][0]=1;b[2][1]=1;b[3][0]=1;b[3][1]=2;b[3][2]=2;b[3][3]=1;
我们观察发现（至少我是观察）b[i][j]=b[i-1][j-i+1]+……b[i-1][j];
注意j-i+1<0时令其为0；j>(i-1)*(i-2)/2,即j大于i-1层逆序对最大值时，b[i][j]=b[i-1][j-i+1]+……b[i-1][n]；
发现有联系区间和则
令a[i][j]表示n=i时，k=1到j所有答案的和
首先发现a[i][0]都为1；
最终a[i][j]=a[i][j-1]+a[i-1][j]-a[i-1][j-i]；注意到之前提到的问题就好答案就是a[n][k]-a[n][k-1]；
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int n,k; int a[1005][1005]; int main() { int i,j,l; scanf("%d%d",&n,&k); a[1][0]=1; a[2][0]=1;a[2][1]=2; a[3][0]=1;a[3][3]=6; a[3][1]=3;a[3][2]=5; for(i=4;i<=n;i++){ a[i][0]=a[i-1][0]; for(j=1;j<=min(k,i*(i-1)/2);j++){ if(j>(i-1)*(i-2)/2)a[i][j]=(a[i][j-1]+a[i-1][(i-1)*(i-2)/2]-a[i-1][j-i])000; else{ if(j-i>=0)a[i][j]=(a[i][j-1]+a[i-1][j]-a[i-1][j-i])000; else a[i][j]=(a[i][j-1]+a[i-1][j])000; } } } printf("%d",(a[n][k]-a[n][k-1]+10000)000); return 0; }