洛谷P1521 求逆序对 题解
2024-09-01 14:43:26
题意:
求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暴力:
#include<cstdio>
int n,m,i,j,k,f[][]; int main()
{
scanf("%d%d",&n,&m);
f[][]=;
for (i=;i<n;++i)
for (j=;j<=(i-)*i>>;++j)
for (k=;k<=i;++k)
if ((f[i+][j+i-k]+=f[i][j])>=) f[i+][j+i-k]-=;
printf("%d\n",f[n][m]);
return ;
}
n^3:
#include<cstdio>
int n,m,i,j,f[][]; int main()
{
scanf("%d%d",&n,&m);
f[][]=;
for (i=;i<=n;++i)
{
for (j=;j<i;++j) f[i][j]=(f[i][j-]+f[i-][j])%;//因为f[i,j]里面统计的是类似于前缀和的一个东西,f[i][j]只比f[i][j-1]多了f[i-1][j]这一项
for (;j<=(i-)*i>>;++j) f[i][j]=(f[i][j-]+f[i-][j]-f[i-][j-i])%;//这时求和的项数确定了,就是i-1项,于是f[i,j]比f[i][j-1]多了f[i-1][j]这一项,少了f[i-1][j-i]这一项
for (;j<=(i-)*i>>;++j) f[i][j]=f[i][((i-)*i>>)-j];//因为数对总数为i*(i-1)/2,而一个数对要么是逆序对要么是顺序对,因此f[i][j]是关于f[i][i*(i-1)/4]呈现中心对称的
}
printf("%d\n",(f[n][m]+)%);
return ;
}
最新文章
- jQuery中方法html()与text()的不同
- URL(待整合到HTTP书中哦)
- 已知树的前序、中序,求后序的java实现&;已知树的后序、中序,求前序的java实现
- Unity3D研究院之动态修改烘培贴图的大小&;脚本烘培场景
- 网页加载图片问题 插件lazyload
- jquery实现radio按纽全不选和checkbox全选的实例
- scroll pagination.js数据重复加载、分页问题
- 清风注解-Swift程序设计语言:Point6~10
- 【linux】 linux gpio操作
- 如何给对话框中的控件发送消息呢?Windows消息分类
- 201521123002 《Java程序设计》第2周学习总结
- Java实现3DES加密--及ANSI X9.8 Format标准 PIN PAN获取PIN BlOCK
- 摆脱命令行,Ubuntu下配置Android开发环境
- AFNetWorking同步请求
- 运用Python计算Π的多少(大致计算)
- Linux下进程的创建过程分析(_do_fork do_fork详解)--Linux进程的管理与调度(八)
- Python_守护进程、锁、信号量、事件、队列
- c#中使用excel
- java28
- windows测试登陆