Problem
给定n,k,求得1~n中有多少种排列使得逆序对个数为k?(n,k<=1000)
Solve
考虑DP:
设f[i][j]为i个数中逆序对数量为j的排列数量
但因为我们并不知道我们这i个数到底是谁,难以通过以前的状态得到
设f[i][j]为将i放入之前的排列后,逆序对数量为k的排列数
此时我们发现可以确定前i-1个数都选择了什么,且通过这种方式我们可以得到1~n的任意一种排列,所以此定义可行。
不难得出状态转移方程为:
因为当前插入的i比前面的数都大,所以可以产生0~i-1个逆序对
但此时算法时间复杂度为\(O(n^3)\) 需要对每个i,j,k枚举,注意到我们每次是对\(f_{i-1,j-i+1}\)到\(f_{i-1,j}\)求和,所以这里每次把\(f_i\)求完之后用sum数组标记前缀和即可
其中解为\(f_{n,k}\),边界略
时间复杂度\(O(n^2)\)
Code(注意取模时可能会让答案变成负数)
#include<bits/stdc++.h>
using namespace std;
int n,k,f[1005][1005],sum[1005];
int main(){
cin>>n>>k;
f[1][0]=1;
for(int i=0;i<=k;i++)sum[i]=1;
for(int i=2;i<=n;i++){
for(int j=0;j<=k;j++){
if(i-1<j)
f[i][j]=(10000+sum[j]-sum[j-i])%10000;
else f[i][j]=sum[j];
f[i][j]%=10000;
}
sum[0]=f[i][0];
for(int j=1;j<=k;j++){
sum[j]=sum[j-1]+f[i][j];
sum[j]%=10000;
}
}
cout<<f[n][k]%10000;
return 0;
}
标签:排列,洛谷,int,sum,个数,P2513,1005,逆序
From: https://www.cnblogs.com/yiweixxs/p/18452536