动物园

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2525 字
N个围栏成环，每个小朋友能看到连续5个围栏；
一本通
练习
正文

/*
原题：T1596 「一本通 5.4 练习 3」动物园 (APIO 2007)
题意：N 个围栏成环，每个小朋友能看到连续 5 个围栏；只要“怕的动物被移走”或“喜欢的动物留着”就高兴。
     决定每栏移走/保留(0/1)，求最多高兴的小朋友数。
思路：窗口长 5，故整个环由前 5 栏状态(fix,共 32 种)唯一决定。枚举 fix 后做 DP：
     状态为当前 5 栏窗口(32 种)，逐窗口转移时第 6 栏在环内为自由位、绕回前 5 栏时为固定位。
     每窗口累计该起点处所有小朋友高兴的个数，取 32 种 fix 的最大值。
复杂度：时间 O(32·N·32)，空间 O(32)，N≤10^4。
易错点：1) 围栏是环形，索引需对 N 取模；
       2) 第 6 栏绕回前 5 栏时必须用 fix 的固定位，不能自由选择；
       3) 小朋友高兴条件是“怕的被移走 或 喜欢的留着”，取反才是“都不满足”。
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N,C;
    if(!(cin>>N>>C)) return 0;
    // 按起点 E 归类小朋友，记录其 5 位窗口内的害怕/喜欢掩码
    vector<vector<pair<int,int>>> ch(N+1);
    for(int i=0;i<C;i++){
        int E,F,L;
        cin>>E>>F>>L;
        int fear=0,like=0;
        for(int j=0;j<F;j++){ int x; cin>>x; int pos=((x-E)%N+N)%N; fear|=(1<<pos); }
        for(int j=0;j<L;j++){ int y; cin>>y; int pos=((y-E)%N+N)%N; like|=(1<<pos); }
        ch[E].push_back({fear,like});
    }
    // happy[E][w]：窗口 w 下，起点 E 处小朋友高兴的个数
    vector<vector<int>> happy(N+1,vector<int>(32,0));
    for(int e=1;e<=N;e++){
        for(int w=0;w<32;w++){
            int cnt=0;
            for(auto& p:ch[e]){
                int fear=p.first, like=p.second;
                bool unhappy = ((w&fear)==fear) && ((w&like)==0);
                if(!unhappy) cnt++;
            }
            happy[e][w]=cnt;
        }
    }
    int ans=0;
    for(int fix=0;fix<32;fix++){          // 枚举前 5 栏状态
        vector<int> dp(32,-1);
        dp[fix]=happy[1][fix];            // 起点 1 的窗口固定为 fix
        for(int e=1;e<N;e++){             // 由窗口 e 推到窗口 e+1
            vector<int> ndp(32,-1);
            for(int w=0;w<32;w++){
                if(dp[w]<0) continue;
                int newFence=e+5;         // 新加入的第 6 栏
                if(newFence<=N){          // 仍在环内，自由位
                    for(int bit=0;bit<2;bit++){
                        int wn=((w>>1)&31)|(bit<<4);
                        int val=dp[w]+happy[e+1][wn];
                        if(val>ndp[wn]) ndp[wn]=val;
                    }
                }else{                    // 绕回前 5 栏，固定位
                    int k=newFence-N;     // 1..4
                    int bit=(fix>>(k-1))&1;
                    int wn=((w>>1)&31)|(bit<<4);
                    int val=dp[w]+happy[e+1][wn];
                    if(val>ndp[wn]) ndp[wn]=val;
                }
            }
            dp=move(ndp);
        }
        for(int w=0;w<32;w++) if(dp[w]>ans) ans=dp[w];
    }
    cout<<ans<<"\n";
    return 0;
}
动物园

正文

一本通·提高篇的其它内容
