【BZOJ2024】[SHOI2009] 舞会（动态规划）
- 有(n)个男人和(n)个女人，每个人有一个身高。
- 先要将他们配成(n)对，满足最多有(k)对中女人比男人高，求方案数。
- (nle200)
动态规划+分类讨论
我们先将所有男人和女人分别按身高排个序，然后设(f_{i,j})表示前(i)个男人和前(i)个女人配对产生(j)个女人比男人高的对的方案数。
然后就是分类讨论。
(i)个女人
首先考虑如果对数不变。
一种情况是第(i)个女人替换了之前某个比配对男人高的配对女人，因为排过序，所以第(i)个女人肯定比这个配对男人高，而那个配对女人肯定不高于第(i)个男人。这一类方案数为(j)。
另一种情况是第(i)个女人替换了之前某个不矮于第(i)个女人的配对男人的配对女人。这与(j)无关，枚举(i)的时候可以直接统计，不妨设为(t)。
显然两种情况不可能重合（重合意味着存在一个比第(i)个女人高的配对男人，他的配对女人比他高，那就更比第(i)个女人高，但实际上我们是排过序了的），所以总方案数就是(j+t)。
而对数变化(1)的情况就是第(i)个女人总共(i)种配对方案减去对数不变的方案，即(i-j-t)。
综上，得到：
[f_{i,j}=(j+t) imes f_{i-1,j}+(i-(j-1)-t) imes f_{i-1,j-1}
]
(i)个女人
其实也是类似的，同样先考虑对数不变。
那么这个女人必须要替换之前某一对男女，满足配对男人矮于配对女人，且配对女人不高于当前男人。
满足配对男人矮于配对女人的对数是(j)，而我们考虑配对女人高于当前男人的必然更高于配对男人（假设这部分人数为(t)），也就是说这(t)种不满足条件的情况是被完全包含在这(j)种情况当中的，所以满足条件的方案数就应该是(j-t)。
对数变化(1)的情况仍旧是第(i)个女人总共(i)种配对方案减去对数不变的方案，即(i-j+t)。
综上，得到：
[f_{i,j}=(j-t) imes f_{i-1,j}+(i-(j-1)+t) imes f_{i-1,j-1}
]
Python
由于这道题并没有给出模数，刚好最近在学习Python，所以偷懒了一些就直接用Python了。
然而似乎因为对Python部分语法理解不够透彻，反而浪费了更长的时间。
(O(n^2))
st=input().split()
n=int(st[0])
k=int(st[1])
a=[0 for i in range(n+1)]
for i in range(n):
a[i]=int(input())
b=[0 for i in range(n+1)]
for i in range(n):
b[i]=int(input())
a.sort()#排序
b.sort()#排序
f=[[0 for i in range(n+5)] for j in range(n+5)]
f[0][0]=1#初始状态
for i in range(1,n+1):
if(a[i]>=b[i]):#如果第i个男人不矮于第i个女人
t=0
for j in range(1,i+1):
t+=(a[j]>=b[i])#统计之前不矮于比第i个女人的男人数量
for j in range(0,i+1):
f[i][j]+=(j+t)*f[i-1][j]#对数不变
for j in range(1,i-t+1):
f[i][j]+=(i-(j-1)-t)*f[i-1][j-1]#对数变化1
else:#如果第i个男人矮于第i个女人
t=0
for j in range(1,i):
t+=(b[j]>a[i])#统计之前高于第i个男人的女人数量
for j in range(t,i+1):
f[i][j]+=(j-t)*f[i-1][j]#对数不变
for j in range(1,i+1):
f[i][j]+=(i-(j-1)+t)*f[i-1][j-1]#对数变化1
t=0
for i in range(k+1):
t+=f[n][i]#统计答案
print(t)