P1240 诸侯安置

· · 题解

首先是一步本鶸想了很久也没有想到的操作。。。

因为将整行/列平移并不影响诸侯间的限制关系，

且题目又说了镜面和旋转的情况属于不同的方案，

那我们就可以把图案平移成我们想要的样子了。

那我们希望图案是什么样子？既然是dp,

我们当然希望能够得到没有后效性的图案。

也就是楼下dalao的图案。

因为每一列的长度都≥前一列的长度，

所以若前j列放了k-1个且第k个放在i列，

那么在这一列放一个的方案便是长度lon[i]-(k-1).

若用f[i][k]表示前i列放了k个

且第i个放在第i列的方案数，则易得

f[i][k]=\sum_{j<i}{f[j][k-1]*(lon[i]-(k-1))}

其中lon[i]表示第i列的长度。

这样做是O(n^3)的.实际上可以优化到O(n^2).

复杂度高一层是因为我们的状态选择的限制多了.

因为实际上,我们不需要第k个放在第i列这一条件。

我们设f[i][k]表示前i列放了k个的方案，则有：

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

原因很简单,取f[i-1][k]代表第i列放0个,

取f[i-1][k-1]*(lon[i]-(k-1))代表第i列放1个.

最终输出f[2*n-1][k].

复杂度O(n^2).

#include<iostream>
#include<algorithm>
#define p 504
using namespace std;

int f[210][210],lon[210];
int main(){
    int n,kk;cin>>n>>kk;
    if(kk>2*n-1){cout<<0;return 0;}
    for(int i=1;i<n;i++)lon[2*i-1]=lon[2*i]=2*i-1;
    lon[2*n-1]=2*n-1;
    for(int i=0;i<=2*n-1;i++)f[i][0]=1;//初始化
    for(int i=1;i<=2*n-1;i++)
    for(int k=1;k<=lon[i];k++){
        f[i][k]=f[i-1][k]+f[i-1][k-1]*(lon[i]-k+1);
        f[i][k]%=p;
    }
    cout<<f[2*n-1][kk];
    return 0;
}