题解：P14236 [COI 2011] 主教 / LOVCI
YouziChenpi · · 题解
P14236 [COI 2011] 主教 / LOVCI
题目大意
在一个
问在两个主教共移动
题意理解
下过棋的应该很快就能发现，两个主教可能看到（或移动到）的格子的集合交集为空集，并集为整个棋盘。没下过棋的看看下面这个图：
对于
题目转化
由题意理解可知，这道题看似是两个主教共用一个棋盘，实则为两个主教在两个独立的棋盘上移动。显然，我们可以分别求出两个主教在自己的棋盘上移动
我们首先对棋盘编号如下（以
01 02 03 04 05 06
07 08 09 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30
31 32 33 34 35 36先看左侧主教（走黑格的），其能走到的格子如下：
01 03 05
08 10 12
13 15 17
20 22 24
25 27 29
32 34 36很明显这样一不方便存图，二不方便查找某个格子能看到哪些格子。于是将棋盘旋转
01
13 08 03
25 20 15 10 05
32 27 22 17 12
34 29 24
36显然，在旋转后，其中任意一个格子能够看到的格子便是和该格子同行或者同列的格子（除了该格子本身）。
同时我们还注意到，我们并不关注格子之间的相对位置，只关注每一个格子能够看到哪些格子。因此，我们将上面那个图按照行长进行排序对计算不产生影响（注意此时是居中对齐）：
25 20 15 10 05
32 27 22 17 12
13 08 03
34 29 24
01
36同理，此时再按照列长进行排序也不会产生影响（左对齐）：
15 20 10 25 05
22 27 17 32 12
08 13 03
29 34 24
01
36再回到原题上来。现在主教的移动方式已经变成了“在不超出棋盘的情况下移动到同行或同列的任意一个格子”。容易发现，每一次的移动都相当于“发现”了新的一行或新的一列（这里只考虑走满不重复的情况），并将其加入答案的集合中。
另外，不移动的情况比较特殊。因为根据规则，如果不移动，那么主教初始位置的价值是不计入答案的，要在最后减掉。而一旦移动过，那么初始位置就一定会被看到，所以只要移动了就不用减掉了。
我们最终只关注“发现”了哪些行列，并不关注顺序。因此将问题变为：选择一些可以互相到达的行和列，使得这些行列的价值之和最大。
解题思路
首先我们需要解决一个问题：什么样的行列之间是可以互相到达的？
前面已经将棋盘按照长度进行排序，因此新的棋盘具有一种性质：若该棋盘上某行与某列有交点，则该行上面的每一行都与该列有交点；同理，该列左侧的每一列都与该行有交点。
由此可以得出：我们所选的最短的那一列一定与所选的最长的那一行有交点；所选的最短的那一行一定与最长的那一列有交点。只要满足了这个条件，我们就一定可以构造出一条合法的路径：先走到最长的那一行，从右往左走完所有所选的列，再从上往下走完所有所选的行。
剩下的问题就是：选取哪些行列时，总价值最大？
首先观察数据范围大概得出算法时间复杂度：题目保证
当选择哪些列已经确定时，棋盘中每一行能带来的额外贡献也就确定了。同时由于总步数和已选列数已经固定，接下来要选择的行数也是固定的。此时只需要贪心地选择行即可。但是在选择时要注意满足上面说的条件。
此时我们计算的是刚好走到
特别地，只移动
另外，处理完一个主教后，将棋盘水平翻转，第二个主教就等价于第一个主教在翻转后棋盘上的情况。这样就可以使用同一份代码处理两个主教，减少码量。
时间复杂度
旋转棋盘
枚举选择哪些列
枚举每一种情况时，有排序
因此总的时间复杂度为
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=25;
const int K=105;
int n,k;
int val[N][N];
int mp[N][N];
int sumr[N],sumc[N],szr[N],szc[N];
int sx,sy;
int dp1[K],dp2[K];
int row,col;
void build(){
row=1;
for(int i=0;i<n;i++){//枚举每一条对角线
for(int a=-1;a<=1;a+=2){//区分对称的两条对角线
if(i==0&&a==1) continue;//避免重复
int tcol=1;//填入第几列
for(int j=0;j<n;j++){
for(int b=-1;b<=1;b+=2){
//映射
int d1=a*(2*i);
int d2=2*n-1+b*(2*j+1);
int r=(d1+d2)/2;
int c=(d2-d1)/2;
if(r>=0&&r<2*n&&c>=0&&c<2*n){
mp[row][tcol]=val[r+1][c+1];
sumr[row]+=val[r+1][c+1];
sumc[tcol]+=val[r+1][c+1];
tcol++;
}
}
}
szr[row]=tcol-1;//记录行长
row++;
}
}
row--;
for(int j=1;j<=2*n;j++){//计算列长
szc[j]=0;
for(int i=1;i<=row;i++){
if(szr[i]>=j) {
szc[j]++;
}
}
}
col=2*n;
while(col>0&&szc[col]==0) col--;
sx=2*(n/2);
sy=2*((n-1)/2)+1;
return;
}
void solve(){
build();//旋转棋盘
memset(dp1,-0x3f,sizeof dp1);
for(int sta=0;sta<=(1<<col);sta++){//枚举选择哪些列
int tmp[N];
memcpy(tmp,sumr,sizeof sumr);
int cnt=0,sum=0,mx=0,mn=row+1;
if(!(sta&(1<<(sy-1)))) continue;//初始列没有被选中
for(int j=1;j<=col;j++){
if(sta&(1<<(j-1))){//这一列被选中了
cnt+=(j!=sy);
sum+=sumc[j];//当前的总价值
mx=max(mx,szc[j]);//更新最大列长
mn=szc[j];//由于是从左往右，列长越来越小，所以每一个都一定是当前的最小值
for(int i=1;i<=szc[j];i++){
tmp[i]-=mp[i][j];//这一个点已经在列中被计算过了，要从行中去掉
}
}
}
if(cnt>k) continue;//选的列太多了
int best=sx;//第一行
if(sx>mn){//起始行不够长
best=1;
for(int i=1;i<=mn;i++){
if(tmp[i]>tmp[best]) {
best=i;
}
}
}
vector<int> rest;//候选的行
for(int i=1;i<=mx;i++){
if(i==sx||i==best){//第一行和起始行必须选
sum+=tmp[i];
cnt+=(i!=sx);
}
else{
rest.push_back(tmp[i]);
}
}
sort(rest.begin(),rest.end(),greater<int>());//按额外的贡献从大到小排序
if(cnt<=k) {
dp1[cnt]=max(dp1[cnt],sum);
}
for(int i=0;i<rest.size();i++){//贪心处理
sum+=rest[i];
cnt++;
if(cnt<=k)dp1[cnt]=max(dp1[cnt],sum);
}
}
dp1[0]-=mp[sx][sy];//不移动时特殊处理
for(int i=2;i<=k;i++)//注意从2开始
dp1[i]=max(dp1[i],dp1[i-1]);
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1;i<=2*n;i++){
for(int j=1;j<=2*n;j++){
cin>>val[i][j];
}
}
solve();//处理主教1
for(int i=1;i<=2*n;i++){//左右翻转棋盘
for(int j=1;j<=n;j++){
swap(val[i][j],val[i][2*n-j+1]);
}
}
memset(mp,0,sizeof mp);//一定要注意清空
memset(sumr,0,sizeof sumr);
memset(sumc,0,sizeof sumc);
memset(szr,0,sizeof szr);
memset(szc,0,sizeof szc);
memcpy(dp2,dp1,sizeof dp1);//存下第一个主教的数据
solve();//处理主教2
int ans=-2e9;
for(int i=0;i<=k;i++){
ans=max(ans,dp1[i]+dp2[k-i]);//两个主教一共走K步
}
cout<<ans;
return 0;
}另外此题还有一个优化没有在代码中实现。仔细思考可以发现，主教是一定不会走到棋盘的角落的，因为走到角落不可能看到任何新的格子。
本文作者有使用不知道哪个版本的 DeepSeek 修改语病。