【洛谷】 P1240 诸侯安置（递推）

本文主要是介绍【洛谷】 P1240 诸侯安置（递推），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

洛谷P1240 诸侯安置

点击此处去OJ
问题描述
很久以前，有一个强大的帝国，它的国土成正方形状（需旋转45°来看），图1所示为n=3时的情况。这个国家有若干诸侯。由于这些诸侯都曾立下赫赫战功，因此国王准备给他们每人一块封地(正方形中的一格)。但是，这些诸侯又非常好战，每当两个诸侯位于同一行或同一列时，他们就会开战。如图2中为n＝3的国土，其中阴影部分表示诸侯所处的位置。其中，前两幅图中的诸侯会互相攻击，第三幅则不会。

国王自然不愿意看到他的诸侯们互相开战，致使国家动荡不安。因此，他希望通过合理地安排诸侯所处的位置，以使他们之间两两无法攻击。
现在，给出正方形的边长n，以及需要封地的诸侯数量k，要求你求出所有可能的安置方案数（n≤l00，k≤2*n-2）。由于方案数可能很多，你只需要输出方案数除以504的余数即可。
（注意：镜面和旋转的情况属于不同的方案）。

输入格式
仅一行，两个整数n和k，中间用一空格隔开。

输出格式
一个整数，表示方案数除以504的余数。

样例输入
2 2

样例输出
4

算法分析

首先要弄清楚，在本题中当n取某个值时，其对应的国土情况是怎样的。

不难看出，无论n取何值，国土的行、列个数均为奇数。接下来我们思考如何求解本题。
对于这一类求“***方案数”，并且还需要将结果对某个数字进行取余的题目而言，往往暗示了其最终结果会很大。此时，通常有两种处理办法：搜索、动态规划。
对于本题而言，搜索算法是很不现实的。因为在用搜索的方式去枚举某个国土的具体分配方案时，递归的层次将取决于k的取值。而我们知道，一个递归算法的递归树如果超过了50层，往往会超时。因此在本题k最大会取到2 ╳ 100 - 2 = 198的情况下，搜索算法是很难完成任务的。另一方面，对于搜索算法枚举出的国土分配方案来说，我们还需要去制定“诸侯们是否会打架？”这个规则，这无疑也会带来一些开销。因此求解本题最合适的方案最终落到了DP的头上。
简单解读一下本题的要求，就是“在一个拥有很多小格子的正方形中分配小格子，且要求分配出去的所有小格子彼此之间都不在同一行或者同一列”。由于要求的格子分配方案是基于任意两个格子之间行、列均不相同而得到的，那么在初始情况下，对整个正方形中的格子在行、列上进行平移是不会影响这个值的。

接下来开始正式分析这道题：
其实它的意思和八皇后挺相似的（简言之：不能同行或同列），不过简单很多。首先有一步很考智商的操作（别问为什么，问就是不知道）：将整行/列平移，其并不影响诸侯间的限制关系，自己想为什么。如下：

之所以要进行这个变换，是因为在它将更方便我们去分析其背后所藏的动态转移方程，你也可以将所有的格子按行向下（上）平移，最终所得结果都是一致的。
就以上图为例，假设当前n=5，k=5（即需要在n=5的国土中安置5个诸侯），那我们要如何计算总方案数呢？为了能更清晰地阐述这个选取过程，我们按序分格子。首先是第一个格子，由于前面我们将所有列平移到了图像的右侧，此时该国土是一个上下对称的图形。因此为了能在后面分格子时具有一定的规律性，我们先将第一个格子选为下图右侧中最左边的那个，如下所示：

接下来分第二个格子。由于第一个格子“占据”了上图所示的国土的上下对称线，因此接下来第二个格子可以占据的位置为其余部分，分别是第一行、第二行、第三行、第四行（或者对称线以下的对称部分）。这里先不考虑对称线的下半部分，我们选择第四行的第一个格子（也可以选择第二个），可以得到如下图所示的分法：

注：这里不考虑对称线的下半部分是出于讨论分析时更容易理解的角度。实际上，怎么选都是可以的。
接下来分别选择第三行、第二行的第一个格子作为此过程中诸侯所分到的格子，如下所示：

当剩下最后一个诸侯时，若我们假设其只能在最后一列中选择格子，那么其可选的位置如下：

由于前面四个诸侯分别将第二行、第三行、第四行、第五行“占据”，因此留给最后一个诸侯的位置就只能是最后一列（含有2*n-1行）中，除开这4行的其余位置。所以在这种情况下，我们不难得出第五个诸侯有 (2*n-1) - (k-1) = 2*n - k = 2*5 - 5 = 5种安置方式。即，在固定了前面k-1个诸侯所分得的格子后，第k个诸侯的安置方式有2*n - k种。
该公式的正确性可以验证。比如当k=6时，我们可以让前面四个诸侯的放置方式与k=5时的放置方式一致，同时将第五个诸侯放置在第四列的最后一排，如下图所示：

这时，对于最后一个诸侯而言，若我们假设其只能在最后一列中选择格子，不难看出其能放置的位置情况如下：
图10
将n=5，k=6带入公式有：2*n - k = 2*5 - 6 = 4，符合上图中的情况。
经检验，将k取值为其余合法值时上述公式的正确性依然成立。
这里需要注意，前面的分析为我们得到的结论是：“在固定了前面k-1个诸侯所分得的格子后，第k个诸侯的安置方式有2*n - k种”。这不是最终的递推式，而只是其中一种特殊情况，因此在前面的分析中我们总是做了这样的假设“对于最后一个诸侯，若我们假设其只能在最后一列中选择格子”。
客观来看，如果我们要在一个给定了n和k的值的国土中为诸侯安置土地，则在所有的安置方案中，对于该国土的最后一列而言，其只会有两种情况：
① 最后一列没有任何诸侯；
② 最后一列被安置了某位诸侯（也就是前面所讨论的情况）。
基于此，若我们假设一个变量f[i][j]，其含义为：在前面i列中，安置j个诸侯有f[i][j]种方案。那么对于任意合法取值，都将满足：

f[i][j] = f[i-1][j] + f[i-1][j-1] * ( len(i) - (k-1) )

其中，f[i-1][j]表示在前面i-1列就已安置完了所有的诸侯时的方案数（即最后一列没有任何诸侯）；f[i-1][j-1] * ( len(i) - (k-1) )表示前i-1列安置j-1个诸侯，最后一列安置最后一个诸侯时的方案数（len(i)表示第i列的长度）。
该式便是求解本题最终的递推式。
现在我们需要做的最后一步是确定初值。由于n最小为1，k最小为0，而由上面的递推式，当k取值为0时（即j=0时）会发生数组越界，因此j在实际的递推过程中需要从1开始迭代。此时有:

f[1][1] = f[0][1] + f[0][0] * ( len(1) - 0) = f[0][1] + f[0][0]

显然，f[0][j]=0（j为正整数），因为这表示没有格子给诸侯分配，因此需要设所有的f[0][j]为0。由于当n=1，k=1时，显然只有一种分配方案，所以f[1][1]=1，因此可以反推出f[0][0]=1。而对于任意的f[i][0]（i为正整数），这都表示“在前面i列中不安置诸侯的分配方法”，所以f[i][0]=1。
故此，我们便确定好了f数组的初值。下面给出本题的完整代码：

完整代码

#include<iostream>
using namespace std;const int N = 205;
const int MOD = 504;
int f[N][N]; 
int len[N]; int main()
{int n,k,i,j;cin>>n>>k;// 特值判定if(k>=2*n-1){cout<<0<<endl;return 0;}	// 设置每一列的长度for(i=1;i<=n;i++)len[2*i-1]=len[2*i]=2*i-1;// 为数组设置初值for(i=0;i<=2*n-1;i++)f[i][0]=1; // 转移方程（递推公式） for(i=1;i<=2*n-1;i++)for(j=1;j<=len[i];j++){f[i][j] = f[i-1][j]+f[i-1][j-1]*(len[i]-(j-1));f[i][j] %= MOD;}cout<<f[2*n-1][k]<<endl; return 0;}