P12663 [KOI 2023 Round 2] 湖边的蚁穴 题解

· · 题解

首先，读一下题，能够有一个结论：如果有小房间时让蚂蚁进小房间为最好的情况。

证明：

因为题目中提到：“当前蚁穴的每条通道最多只能连接一只住着蚂蚁的位置”，所以进小房间我们就能保证目前的大房间一定没有蚂蚁住，从而使附近的两个房间均可居住。

接下来，可以枚举两种情况：

  1. 从一号房间开始居住；
  2. 从二号房间开始居住。

循环体内进行以下几个操作：

  1. 判断当前房间 i 是否有小房间，如果有，答案加上小房间数；
  2. 若前一个或后一个房间有小房间并且前一个房间没有蚂蚁居住，答案加 1，并标记当前房间有蚂蚁；
  3. 若前一个房间没有蚂蚁居住，答案加 1 ，并标记当前房间有蚂蚁。

需要注意的是，从一号房间开始住的话需要判断 1 号和 n 号房间是否同时有蚂蚁居住，如果有，答案减 1。

具体代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans,cnt;
struct node{
    int pd,so,c;//pd表示是否有小房间，so表示小房间数，c表示是否选择过
}e[250010],e1[250010];//e表示情况1，e1表示情况2 
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>e[i].so,e[i].pd=((e[i].so)?1:0),e1[i]=e[i];//预处理，判断是否有小房间 
    for(int i=1;i<=n;i++)//情况1
        if(e[i].pd) cnt+=e[i].so;
        else if((e[i+1].pd||e[i-1].pd)&&!e[i-1].c) cnt++,e[i].c=1;
        else if(!e[i-1].c) cnt++,e[i].c=1;
    if(e[1].c&&e[n].c) cnt--;//特判 
    ans=max(ans,cnt);//记录答案 
    cnt=0;
    for(int i=2;i<=n;i++)//情况2 
        if(e1[i].pd) cnt+=e1[i].so;
        else if((e1[i+1].pd||e1[i-1].pd)&&!e1[i-1].c) cnt++,e1[i].c=1;
        else if(!e1[i-1].c) cnt++,e1[i].c=1;
    ans=max(ans,cnt);
    cout<<ans;//输出答案
    return 0; 
}