题解 SP64 【PERMUT1 - Permutations】
Snowflake_Pink
2018-12-08 22:07:34
~~我会告诉你这是三倍经验题吗。。。~~
做完这道你可以去做[P1521 求逆序对](https://www.luogu.org/problemnew/show/P1521)和[P2513 [HAOI2009]逆序对数列](https://www.luogu.org/problemnew/show/P2513)
~~但是我并不确定我的代码在P2513不会TLE~~
------------
在这道题中，你会发现你逆序对的个数只和**相对大小有关**！！
然后就可以建立DP模型：dp[i][j]表示i个不同的数的所有排列中，逆序对数量为j的排列个数。初始边界为dp[1][0]=1。
关于dp方程：当有i-1个数时，有j-1个逆序对时，添加第i个数，必有一个位置刚好使逆序对数+1，即可转移到dp[i][j]。同理j-2,j-3……j-(i-1),因为只有i-1个数，所以最多到i-1,当然也可能不增加逆序对。
Code：
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,k,w;
int dp[1001][1001];
int main(){
scanf("%d",&w);
while (w--){
memset(dp,0,sizeof (dp));
scanf("%d%d",&n,&k);
dp[1][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
for(int l=0;l<i;l++){
if(j>=l)
dp[i][j]+=dp[i-1][j-l];
}
}
}
printf("%d\n",dp[n][k]);
}
return 0;
}
```
本蒟蒻第一篇题解。有什么不好的地方可以私信留言哈~~~
^_^