首页 > 代码库 > 洛谷P1521 求逆序对 题解
洛谷P1521 求逆序对 题解
题意:
求1到n的全排列中有m对逆序对的方案数。
思路:
1.f[i][j]表示1到i的全排列中有j对逆序对的方案数。
2.显然,1到i的全排列最多有(i-1)*i/2对逆序对,而对于f[i][j]来说,新加入一个数i+1,产生的新的逆序对数与插入的位置有关(数目为插入的数的位置之后的数的数目),于是n^4暴力就新鲜出炉了。
3.换一个角度来说,当i>j的时候,我们枚举i的全排列的第一位的数字,如果是1,那么就要求剩下i-1个数中有j个全排列,如果是2,要求剩下i-1个数中有i-2个
全排列,依次类推,得到了第一个方程:f[i][j]=sum{f[i-1][0],f[i-1][1],f[i-1][2].....f[i-1][j]}
当i<=j的时候,由于i的全排列中最大的数字是i,所以把i放到第一位上,由第一位最多能能产生i-1个逆序对,把1放到第一位上能产生0个逆序对,所以i-1-1+1=i-1,这时的f[i][j]就要由f[i-1][j]开始算上他自己,总共i-1项的和。因此:f[i][j]=sum{f[i-1][j],f[i-1][j-1],f[i-1][j-2].....f[i-1][j-i+1]}
反思:
我只会暴力,优化只能理性愉悦一下了,好菜啊……
代码:
n^4暴力:
1 #include<cstdio> 2 int n,m,i,j,k,f[201][10000]; 3 4 int main() 5 { 6 scanf("%d%d",&n,&m); 7 f[1][0]=1; 8 for (i=1;i<n;++i) 9 for (j=0;j<=(i-1)*i>>1;++j) 10 for (k=0;k<=i;++k) 11 if ((f[i+1][j+i-k]+=f[i][j])>=10000) f[i+1][j+i-k]-=10000; 12 printf("%d\n",f[n][m]); 13 return 0; 14 }
n^3:
1 #include<cstdio> 2 int n,m,i,j,f[101][5000]; 3 4 int main() 5 { 6 scanf("%d%d",&n,&m); 7 f[1][0]=1; 8 for (i=2;i<=n;++i) 9 { 10 for (j=0;j<i;++j) f[i][j]=(f[i][j-1]+f[i-1][j])%10000;//因为f[i,j]里面统计的是类似于前缀和的一个东西,f[i][j]只比f[i][j-1]多了f[i-1][j]这一项 11 for (;j<=(i-1)*i>>2;++j) f[i][j]=(f[i][j-1]+f[i-1][j]-f[i-1][j-i])%10000;//这时求和的项数确定了,就是i-1项,于是f[i,j]比f[i][j-1]多了f[i-1][j]这一项,少了f[i-1][j-i]这一项 12 for (;j<=(i-1)*i>>1;++j) f[i][j]=f[i][((i-1)*i>>1)-j];//因为数对总数为i*(i-1)/2,而一个数对要么是逆序对要么是顺序对,因此f[i][j]是关于f[i][i*(i-1)/4]呈现中心对称的 13 } 14 printf("%d\n",(f[n][m]+10000)%10000); 15 return 0; 16 }
洛谷P1521 求逆序对 题解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。