2 排队
(lineup.pas/.c/.cpp)
【问题描述】
小sin所在的班有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）都是可行的排法。小sin想知道总共有多少种可行排法。
【输入】
输入文件名为lineup.in。
一行两个整数n和k，意义见问题描述。
【输出】
输出文件名为lineup.out。
输出一个整数，表示可行排法数。由于结果可能很大，请输出排法数mod 1799999的值。
【输入输出样例】
|
lineup.in |
lineup.out |
|
5 3 |
15 |
【数据范围】
对于20%的数据，有n≤10，k≤40；
对于60%的数据，有n≤100，k≤500；
对于100%的数据，有n≤100，k≤n*(n-1)/2。
解题报告
像这样的题，也正如这套题一样的完全是思考的时间多。（哎，说得好像我做出来了一样，但其实我连样例都没有去想“天，15个，算了不想了。”所以啊，还是要有耐心，考场上一定要静下来，不要急躁，有同学用了两个小时找规律，最终不负有心人，全过了。）
首先，我们需要找规律，而找规律不是随机就找到了，需要观察和对比两组甚至多组数据。于是，打开打表模式：
nk 0 1 2 3 4 5 6
1 1 0 0 0 0 0 0
2 1 1 0 0 0 0 0
3 1 2 2 1 0 0 0
4 1 3 5 6 5 3 1
5 1 4 9 15 20 22 20 .......
每一个n都有一个k的数量的限制，即长度 l ，如果k>l 就为0 ，l =0,1,3,6,等等。l+=i-1; 每一次都是在上一次的基础上添一个比上一次最大值大1的数，如下：
上一次：1 2 3 4 5
这一次添一个6 有6 种添法：在5后，在4~5间，在3~4间，在2~3间，在1~2间，在1前；
分别有6种增加的可能性： 不影响，多一组， 多两组， 多三组， 多四组， 多五组
因此可以列出方程：f[i][j]( i 个数，取 j 组)=f[i-1][j]+f[i-1][j-1]+...+f[i-1][j-i+1]
(转换)：f[i][j-1]=f[i-1][j-1]+f[i-1][j-2]+...+f[i-1][j-i]
(二式相减)：f[i][j]=f[i][j-1]+f[i-1][j]-f[i-1][j-i]
方程有了，代码就简单多了。
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int n,k; 5 int f[105][5005]; 6 const int inf=1799999; 7 int main() 8 { 9 freopen("lineup.in","r",stdin); 10 freopen("lineup.out","w",stdout); 11 cin>>n>>k; 12 int l=0; 13 for (int i=1;i<=n;i++) 14 { 15 l+=i-1; 16 f[i][0]=1; 17 for (int j=1;j<=k;j++) 18 { 19 if (j>l) break; 20 f[i][j]=(f[i-1][j]+f[i][j-1])%inf; 21 if (j-i>=0) f[i][j]=(f[i][j]-f[i-1][j-i]+inf)%inf; 22 } 23 } 24 cout<<f[n][k]; 25 return 0; 26 }