插头dp

dk_qwq · 2023-10-07 19:07:40 · 算法·理论

是否需要记录 边框(侧边)

状态是否有方向性,若没有则可直接使用长度为n的表示法 否则记录整个轮廓线

最小表示法

状态 22011 虽与状态 11022 等价,但为保证复杂度以及避免奇奇怪怪的bug需要转化为字典序最小的形式

auto encode=[&ans](int state,int res){
    int vis[N];
    for(int i=0;i<=n;i++) vis[i]=0;
        int cnt=0;
    for(int i=0;i<=n;i++){
        int x=(state>>bits[i])%8;
        if(x==0) continue;
        if(!vis[x]) vis[x]=++cnt;
        state+=cnt*(1<<bits[i])-x*(1<<bits[i]);
    }
    if(cnt<2) ans=max(ans,res);
    return state;
};