排队(递推 \(\star \))
- 小花所在的班有 \(n\) 名同学(任何两位同学身高不相同),正准备排成一列纵队,但他们不想按身高从矮到高排,那样太单调,太没个性。
- 他们希望恰好有 \(k\) 对同学是高的在前,矮的在后,其余都是矮的在前,高的在后。如当 \(n=5,k=3\) 时,假设\(5\) 人从矮到高分别标为 \(1,2,3,4,5\),则 \((1,5,2,3,4),(2,3,1,5,4),(3,1,4,2,5)\)都是可行的排法。
- 小花想知道总共有多少种可行排法。
Input
- 一行两个整数 \(n\) 和 \(k\),意义见问题描述。
Output
- 输出一个整数,表示可行排法数。由于结果可能很大,请输出排法数 \(mod\ 1799999\) 的值。
Sample Input
5 3
Sample Output
15
Hint
- 对于 \(20\%\) 的数据,有 \(n≤10,k≤40\);
- 对于 \(60\%\) 的数据,有 \(n≤100,k≤500\);
- 对于 \(100\%\) 的数据,有 \(n≤100,k≤\frac{n*(n-1)}{2}\)。
- 来源:\(20180715\)
分析
- \(1\sim n\) ,组成的序列中,如果升序时,逆序对数位 \(0\) ,倒序时逆序对数为:\(1+2+...+n-1\)。
- 定义 \(f[i][j]\) 表示 \(1\sim i\) 组成的序列,逆序对个数为 \(j\) 时的方案数。
- 则有:\(f[i][j]=f[i-1][j]+f[i-1][j-1]+...+f[i-1][j-i+1]\) \((1)\)
- \(i\) 是当前最大的数,把 \(i\) 放到 \(1\sim i-1\) 的序列中可以控制 \(i\) 的位置增加 \(0\sim i-1\) 对逆序对。
- 同理:\(f[i][j-1]=f[i-1][j-1]+f[i-1][j-2]+...+f[i-1][j-i]\) \((2)\)
- \((1)-(2)\) 移项可得:\(f[i][j]=f[i][j-1]+f[i-1][j]-f[i-1][j-i]\) 。
Code
#include <bits/stdc++.h>
typedef long long LL;
const int maxn=100+5,Mod=1799999;
LL f[maxn][maxn*maxn];//f[i][j]前i个数组成j个逆序对的方案数
int n,k,sum;
void Solve(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
f[i][0]=1;//0对逆序对方案数位1,即升序
for(int i=1;i<=n;i++){
sum+=i-1;
for(int j=1;j<=k;j++){
if(j>sum)break;//i个人顶多sum个逆序对,倒序
f[i][j]=(f[i][j-1]+f[i-1][j])%Mod;
if(i<=j)
f[i][j]=(f[i][j]-f[i-1][j-i]+Mod)%Mod;
}
}
printf("%lld\n",f[n][k]%Mod);
}
int main(){
Solve();
return 0;
}
原文链接: https://www.cnblogs.com/hbhszxyb/p/13265862.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/363744
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!