题解 P5422 【[USACO19OPEN]Compound Escape P】

Time_tears · 2020-09-11 14:59:50 · 题解

本题是一道很好的轮廓线 Dp，希望这篇题解能对你有所帮助，点个赞吧。

直接进入正题，我们怎么来考虑轮廓线我们设 f_{s} 表示最下面的连通情况 。

首先我们初始化第 0 行，这一部分就只需要枚举一个 O(2^{3*n } ) 的状态 s ，把 s 的最小连通情况 (连通块从零开始编号)（这里连通块一定是相邻的，所以直接算）表示出来后，我们就可以开始 Dp 了。

我们考虑怎么转移到 i,j ，有这么几种情况：

1. j=0

这里又可以分为两种情况

代码一定不要抄噢。

#include<cstdio>
#include<iomanip>
#include<cstring>
#define N 30005
#define M (1<<18)+5
#define ll long long
#define mod 1000000007
#define O4 __inline__ __attribute__((always_inline))
using namespace std;
int las=1,cnt[M][7],tr[M][7];
int n,k,now,he[N][7],su[N][7],vis[M];
const int Mxdt=180000;
O4 char gc() {
    static char buf[Mxdt],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxdt,stdin),p1==p2)?EOF:*p1++;
}
O4 int read() {
    int res=0,bj=0;
    char ch=gc();
    while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=gc();
    while(ch>='0'&&ch<='9')res=(res<<3)+(res<<1)+(ch^48),ch=gc();
    return bj?-res:res;
}
O4 int Mod(int x) {
    return x<=mod?x:x-mod;
}
struct at {
    ll val;
    int cnt;
    at() {
        val=1e18,cnt=0;
    } at(ll _v,int _c):val(_v),cnt(_c) {}
};
O4 at operator *(at a,at b) {
    return (a.val!=b.val)?(a.val<b.val?a:b):(at(a.val,Mod(a.cnt+b.cnt)));
}
O4 at operator +(at a,ll b) {
    return at(a.val+b,a.cnt);
}
struct Node {
    pair<at,bool>val[M];
    int s[M],top;
    Node() {}
    O4 void clear() {
        for(int i=1; i<=top; ++i)val[s[i]].second=0;
        top=0;
    }
    at &operator[](int x) {
        if(!val[x].second)val[x]=make_pair(at(),1),s[++top]=x;
        return val[x].first;
    }
} dp[2];
O4 void Init(ll val=0) {
    for(int st=0,s=0,ct=0; st<(1<<k-1); dp[now][s]=at(val,1),++st,s=ct=val=0)
        for(int t=1; t<k; ++t)((st&(1<<t-1))?val+=he[0][t]:++ct),s|=ct<<(t*3);
}
O4 int Get(int s,int x) {
    return (s>>3*x)&7;
}
O4 int Change(int s,int x,int y) {
    return s^((Get(s,x)^y)<<3*x);
}
O4 void Work(int s,int x) {
    for(int i=0; i<k; ++i)
        if(Get(s,i)==x&&++cnt[s][x]>1)return;
}
O4 void CSH(int s) {
    if(vis[s])return;
    static int cnt,tmp,id[7];
    memset(id,-1,sizeof(id)),cnt=0,tmp=s;
    for(int i=0,x; i<k; ++i)x=Get(s,i),s=Change(s,i,(~id[x])?id[x]:id[x]=cnt++);
    return vis[tmp]=s,void();
}
O4 void Merge(int s,int x) {
    int t1=Get(s,x-1),t2=Get(s,x),tmp=s;
    if(t1==t2)return tr[tmp][x]=s,void();
    for(int i=0; i<k; ++i)if(Get(s,i)==t2)s=Change(s,i,t1);
    tr[tmp][x]=s;
}
O4 void Calc(int s) {
    static int vis[M]= {0};
    if(vis[s])return;
    vis[s]=1,CSH(s);
    for(int i=0; i<k; ++i)CSH(Change(s,i,6));
    for(int i=1; i<k; ++i)Merge(s,i),CSH(tr[s][i]);
    for(int i=0; i<k; ++i)Work(s,i);
    for(int i=1; i<k; ++i)CSH(Change(s,i,Get(s,i-1)));
}
O4 void Update(int s,at x) {
    dp[now][vis[s]]=dp[now][vis[s]]*x;
}
int main() {
    n=read(),k=read();
    for(int i=0; i<n; ++i)for(int j=1; j<k; ++j)he[i][j]=read();
    for(int i=0; i<k; ++i)for(int j=1; j<n; ++j)su[j][i]=read();
    Init();
    for(int i=1; i<n; ++i)
        for(int j=0,x; j<k; ++j) {
            now^=1,las^=1,dp[now].clear();
            for(int t=1,s; t<=dp[las].top; ++t) {
                at atom=dp[las][s=dp[las].s[t]];
                if(Calc(s),!j) {
                    Update(s,atom+su[i][j]);
                    if(cnt[s][Get(s,j)]>1)Update(Change(s,j,6),atom);
                } else {
                    Update(s,atom+su[i][j]);
                    if(cnt[s][Get(s,j)]>1)Update(Change(s,j,Get(s,j-1)),atom+he[i][j]),Update(Change(s,j,6),atom);
                    if(Get(s,j)!=Get(s,j-1))Update(tr[s][j],atom+(su[i][j]+he[i][j]));
                }
            }
        }
    printf("%d\n",dp[now][0].cnt);
    return 0;
}