動態規劃問題複習

蜜汁信仰。全局变量能A题。。

「插頭dp」「連通性dp」(爲什麼不叫CDQdp啊。。。

Case #1: 哈密頓迴路&括號路徑

比較模板化和形式化的dp。暖手系列。選擇BFS式的轉移。

struct cry_hash{
    int hs[MAXM];
    int cnt;
    int sta[MAXM];
    int f[MAXM];
    inline void clear()
    {
        while (cnt)
        {
            hs[sta[cnt]]=0;
            sta[cnt]=f[cnt]=0;
            cnt--;
        }
    }
    inline void push(const int &x)
    {
        if (hs[x])
            f[hs[x]]=max(f[hs[x]],mx);
        else
        {
            cnt++;
            hs[x]=cnt;
            sta[cnt]=x;
            f[cnt]=mx;
        }
    }
}h[2];

int get(const int &sta,const int &i){
    if (sta&pw[lch(i)])
    {
        if (sta&pw[rch(i)])
            return 2;
        else
            return 1;
    }
    else
        return 0;
}

int GT(const int &sta,const int &i){
    return (sta&pw[lch(i)])|(sta&pw[rch(i)]);
}

int gr(const int &sta,const int &aim){
    int tmp=0;
    int cnt=0;
    REP(i,aim,m)
    {
        tmp=get(sta,i);
        if (tmp==1) cnt++;
        else if (tmp==2) cnt--;

        if (!cnt) return i;
    }
    return -1;
}

int gl(const int &sta,const int &aim){
    int tmp=0;
    int cnt=0;
    REPD(i,aim,0)
    {
        tmp=get(sta,i);
        if (tmp==1) cnt++;
        else if (tmp==2) cnt--;

        if (!cnt) return i;
    }
    return -1;
}

void push_all(int i,int j,const int &sta){
    int ns;
    int x,y;
    int aim;
    x=get(sta,j-1);
    y=get(sta,j);
    ns=sta;
    if (x && y)
    {
        ns^=GT(sta,j-1);
        ns^=GT(sta,j);
        if (x==1 && y==1)
        {
            aim=gr(sta,j);
            ns^=pw[rch(aim)];
            h[nxt].push(ns);
        }
        else if (x==2 && y==2)
        {
            aim=gl(sta,j-1);
            ns^=pw[rch(aim)];
            if (j==m)
                h[nxt].push(ns<<2);
            else
                h[nxt].push(ns);
        }
        else if (x==2 && y==1)
            h[nxt].push(ns);
        else if (x==1 && y==2)
        {
            if (!ns)
                ans=max(ans,mx);
        }
    }
    else if (x)
    {
        if (i!=n)
        {
            if (j==m)
                h[nxt].push(ns<<2);
            else
                h[nxt].push(ns);
        }
        if (j!=m)
        {
            ns^=GT(sta,j-1);
            ns^=pw[lch(j)];
            if (x==2) ns^=pw[rch(j)];
            h[nxt].push(ns);
        }
    }
    else if (y)
    {
        if (j!=m)
            h[nxt].push(ns);
        if (i!=n)
        {
            ns^=GT(sta,j);
            ns^=pw[lch(j-1)];
            if (y==2) ns^=pw[rch(j-1)];
            if (j==m)
                h[nxt].push(ns<<2);
            else
                h[nxt].push(ns);
        }
    }
    else
    {
        if (i!=n && j!=m)
        {
            ns^=pw[lch(j-1)];
            ns^=pw[lch(j)];
            ns^=pw[rch(j)];
            h[nxt].push(ns);
        }

        ns=sta;
        mx-=p[i][j];
        if (j==m)
            h[nxt].push(ns<<2);
        else
            h[nxt].push(ns);
    }
}

void work()
{
    cur=0;
    nxt=1;
    mx=0;
    h[cur].push(0);
    REP(i,1,n)
        REP(j,1,m)
        {
            h[nxt].clear();
            REP(k,1,h[cur].cnt)
            {
                mx=h[cur].f[k]+p[i][j];
                push_all(i,j,h[cur].sta[k]);
            }
            nxt^=1;
            cur^=1;
        }
    printf("%d\n",ans);
}

「HNOI 2007」park
一條迴路,隨時可以封閉。
「Ural 1519」
一條迴路,最後封閉。
這種插頭dp一定要熟練。
我們看看HN諸神的跑法

ID Time MEM
tgopknight 0.171 59546 KB
Owaski 0.156 54434 KB
zxozxo 0.343 64890 KB
Dash 0.375 53834 KB
zhangzj 0.156 54478 KB
r_64 0.968 63690 KB
huyating 0.249 1180 KB
Logic 0.109 1417 KB

感覺大爺們都不屑於寫奇怪的做法。。
不過還是蠻優秀的。

ID Time MEM
Prime21 0.046 992 KB

板子還是挺優秀的。。

「BZOJ CITY」一样的题。也是模板练习。
「eat」模拟赛的瘠薄题。强行开大范围矩乘优化, 然后还要加上每次在端点处爆枚。类似于一个dp套插头dp?

const int mo = 1e9+7;
const int MAXN = 20;
const int MAXS = 270;
const int MAXM = 2020;

int pw[30]={0};

long long n;
int m;
int c,d;
poi yy[MAXN],nn[MAXN];

int b;
long long ban[MAXN*2];

int t;
int in[MAXS];
int que[MAXS];

int all;

int tot;
int to[MAXM];
int val[MAXM];
int sz[MAXM];
int nxt[MAXM];
int hd[MAXS];

int inc;
struct cry_hash{
    int in[MAXS*4];
    int f[MAXS*4];
    int q[MAXS*4];
    int tot;
    inline void clear(){
        while (tot)
        {
            in[q[tot]]=0;
            tot--;
        }
    }
    inline void push(const int &sta){
        if (in[sta])
        {
            f[in[sta]]+=inc;
        }
        else
        {
            tot++;
            q[tot]=sta;
            in[sta]=tot;
            f[tot]=inc;
        }
    }
}H[2];

int get_id(int sta){
    if (!in[sta])
    {
        que[++t]=sta;
        in[sta]=t;
    }
    return in[sta];
}

int t1,t2;

// j-1 j
// j*2 j*2+1
int GT(const int &j,const int &sta){
    if (pw[lch(j)]&sta){
        if (pw[rch(j)]&sta)
            return 2;
        else
            return 1;
    }
    return 0;
}
int gt(const int &j,const int &sta){
    return (pw[lch(j)]&sta) | (pw[rch(j)]&sta);
}
int fdr(const int &j,const int &sta){
    int now=0;
    int tmp=0;
    REP(i,j,m){
        tmp=GT(i,sta);
        if (tmp==1) now++;
        else if (tmp==2) now--;
        if (now==0) return i;
    }
    debug("f**k\n");
    return -1;
}
int fdl(const int &j,const int &sta){
    int tmp=0;
    int now=0;
    REPD(i,j,0){
        tmp=GT(i,sta);
        if (tmp==1) now++;
        else if (tmp==2) now--;
        if (now==0) return i;
    }
    return -1;
}

void push_all(const int &j,const int &sta){
    int p=GT(j-1,sta),q=GT(j,sta);
    int ns=sta;
    if (p && q)
    {
        int aim;
        ns^=gt(j-1,sta);
        ns^=gt(j,sta);
        if (p==1 && q==1){
            aim=fdr(j,sta);
            ns^=pw[rch(aim)];
            H[t2].push(ns);
        }
        else if (p==2 && q==2){
            aim=fdl(j-1,sta);
            ns^=pw[rch(aim)];
            H[t2].push(ns);
        }
        else
            H[t2].push(ns);
    }
    else if (p)
    {
        H[t2].push(ns);
        if (j!=m)
        {
            ns^=gt(j-1,sta);
            ns^=pw[lch(j)];
            if (p==2) ns^=pw[rch(j)];
            H[t2].push(ns);
        }
    }
    else if (q)
    {
        if (j!=m)
            H[t2].push(ns);
        ns^=gt(j,sta);
        ns^=pw[lch(j-1)];
        if (q==2) ns^=pw[rch(j-1)];
        H[t2].push(ns);
    }
    else
    {
        if (j!=m)
        {
            ns^=pw[lch(j-1)];
            ns^=pw[lch(j)];
            ns^=pw[rch(j)];
            H[t2].push(ns);
        }
    }
}
void push_non(const int &j,const int &sta){
    int p=GT(j-1,sta),q=GT(j,sta);
    if (p==0 && q==0)
        H[t2].push(sta);
}

void add(const int &x,const int &y,const int &size,const int &vl){
    tot++;
    to[tot]=y;
    val[tot]=vl;
    sz[tot]=size;
    nxt[tot]=hd[x];
    hd[x]=tot;
}

void expand(int nw){
    int sta=que[nw];
    REP(s,0,all)
    {
        H[0].clear();
        inc=1;
        H[0].push(sta<<2);
        t1=0;
        t2=1;
        REP(i,1,m)
        {
            H[t2].clear();
            if (s&(1<<(i-1)))
                REP(j,1,H[t1].tot)
                {
                    inc=H[t1].f[j];
                    push_all(i,H[t1].q[j]);
                }
            else 
                REP(j,1,H[t1].tot)
                {
                    inc=H[t1].f[j];
                    push_non(i,H[t1].q[j]);
                }
            t1^=1;
            t2^=1;
        }

        int id;
        REP(i,1,H[t1].tot)
        if ((H[t1].q[i]&pw[lch(m)])==0)
        {
            id=get_id(H[t1].q[i]);
            add(nw,id,H[t1].f[i],s);
        }

    }
}

struct matrix{
    long long x[12][12];
}A,I,S[70];

matrix operator * (const matrix &a,const matrix &b){
    matrix ret={0};
    REP(i,1,t)
    REP(j,1,t)
    REP(k,1,t)
        (ret.x[i][j]+=a.x[i][k]*b.x[k][j])%=mo;
    return ret;
}

matrix fpm(long long k){
    matrix ret=I;
    int now=0;
    while (k)
    {
        if (k&1) ret=ret*S[now];
        now++;
        k>>=1;
    }
    return ret;
}

long long F[12];
long long G[12];

void init()
{
    pw[0]=1;
    REP(i,1,22) pw[i]=pw[i-1]<<1; 
    RII(n,m);
    RII(c,d);

    REP(i,1,c) RII(nn[i].fr,nn[i].sc),ban[++b]=nn[i].fr;
    REP(i,1,d) RII(yy[i].fr,yy[i].sc),ban[++b]=yy[i].fr;
    ban[++b]=n+1;
    sort(nn+1,nn+1+c);
    sort(yy+1,yy+1+d);
    sort(ban+1,ban+1+b);
    b=unique(ban+1,ban+1+b)-ban-1;

    all=(1<<m)-1;
    get_id(0);
    int now=1;
    while (now<=t) 
    expand(now++);

    REP(i,1,t) I.x[i][i]=1;
    REP(p,1,t)
    {
        for (int i=hd[p];i;i=nxt[i])
            A.x[p][to[i]]+=sz[i];
    }

    long long NN=1;
    int lim=0;
    S[lim]=A;
    while (NN<=n)
    {
        lim++;
        S[lim]=S[lim-1]*S[lim-1];
        NN<<=1;
    }
}

void work()
{
    matrix trans;
    long long now=0;
    int yes,no;
    int ty,tn;
    int cc=1,dd=1;
    F[1]=1;
    REP(x,1,b){
        trans=fpm(ban[x]-1-now);

        MS(G,0);
        REP(i,1,t)
            REP(j,1,t)
                (G[j]+=F[i]*trans.x[i][j])%=mo;

        if (x!=b)
        {
            yes=no=0;
            while (cc<=c && nn[cc].fr==ban[x]) no|=pw[nn[cc].sc-1],cc++;
            while (dd<=d && yy[dd].fr==ban[x]) yes|=pw[yy[dd].sc-1],dd++;
            REP(i,1,m) if (yes&pw[i-1]) if (no&pw[i-1]) no^=pw[i-1];
        }
        else
            yes=0,
            no=all;
        MS(F,0);
            REP(p,1,t)
                for (int i=hd[p];i;i=nxt[i])
                {
                    ty=val[i];
                    tn=all^ty;
                    if ((ty&yes)==yes && (tn&no)==no)
                        (F[to[i]]+=G[p]*sz[i]%mo)%=mo;
                }

        now=ban[x];
    }
    printf("%lld\n",F[1]);
}

int main()
{
    open();
    int _=0;
    init();
    work();
    close();
    return 0;
}

事实证明这个题并不是非常恶心。
「清华集训2014 简单回路」
为什么会说上一题不恶心呢?因为我发现了这道所谓的插头dp基本练习题(雾)「仅考察选手对插头dp的理(shu)解(lian)程度」

Case #1: 联通块为状态的连通性dp

「ZOJ 2126. Rocket Mania」
好题哦。雾。
1.打牌形式,按列而行,逐个dp。考虑到问题本身就是从左连右,列与列直接直接转移复杂度太高,根本无法承受。
2.连通性表示,我们把所有当前状态下相连的插头用标号最小的那个作为这些插头们的状态标号。
这样通过一个vector我们得到状态的连通性表示。
3.状态表示,我们还需要记录每一个插头连通块是否与左端相连,这样又需要一个vector。
4.转移方式枚举每一个格子的4种旋转角度,修改插头直接的连通性。
大致有以下:
a.删除一个插头
b.新增一个连通块
c.添加一个插头入某一个连通块
d.合并两个连通块
5.打牌形式,用传统的大力for循环可能会造成TLE(我还没写完,只是猜测。我们应该使用BFS+hash表的形式卡过去。
6.常数优化:
a.开很多全局变量减少参数传递
b.取一个好的模数。
c.如果一个状态已经没有任何一个连通块与左端相连就ban掉,这个状态已经不可能在连通了。
d.剪掉所有无用插头,即自行连通独立且不与左端相连。(因为之后这个插头可有可无不会改变连通性。

#include <stdio.h>
#include <cstdlib>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <assert.h>
#include <vector>

#define REP(I,A,B) for(int I=A,_END_=B;I<=_END_;I++)
#define REPD(I,A,B) for(int I=A,_END_=B;I>=_END_;I--)
#define RI(X) scanf("%d",&X)
#define RII(X,Y) RI(X),RI(Y)
#define RIII(X,Y,Z) RI(X),RI(Y),RI(Z)
#define RL(X) X=Readint()
#define RLL(X,Y) RL(X),RL(Y)
#define RLLL(X,Y,Z) RL(X),RL(Y),RL(Z)
#define RS(X) scanf("%s",X)
#define RD(X) scanf("%lf",&X)
#define GCH getchar()
#define PCH(X) putchar(X)
#define MS(X,Y) memset(X,Y,sizeof(X))
#define MC(X,Y,var,len) memcpy(X,Y,sizeof(var)*(len))
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define pb(X) push_back(X)
#define mp(A,B) make_pair(A,B)
#define fr first
#define sc second
#define lch(p) (p+p)
#define rch(p) (p+p+1)
#define lowbit(X) ((X)&(-(X)))

using namespace std;

typedef pair<int,int> poi;
typedef vector<int> vi;

inline long long Readint()
{
    long long ret=0;
    int f=1;
    char ch;
    do
    {
        ch=GCH;
        if (ch=='-') f*=-1;
    }while(ch>=0 && (ch<'0' || ch>'9'));

    while ('0'<=ch && ch<='9')
    {
        ret=ret*10+ch-'0';
        ch=GCH;
    }
    return ret*f;
}

void open()
{
    freopen("rocketmania.in","r",stdin);
    freopen("rocketmania.out","w",stdout);
}
void close()
{
    fclose(stdin);
    fclose(stdout);
}

const int MAXN = 11; 
const int MAXS = 1e6;
const int MAXQ = 1e6;
const int mo = 10007;
int BURN = (1<<10)-1;

long long pw[MAXN];
long long tw[MAXN];

short a[MAXN][MAXN][5];
int n,m;

//focus the sta
// 2^10 burning 10 dig -> 10 plug

// the code by cryime21 orz cryname512

struct cry_hash
{
    int hd[mo];
    long long st[MAXS];
    int nxt[MAXS];
    int cnt;

    int now;

    inline void init(){
        cnt=0;
        MS(hd,0);
    }

    inline void push(long long sta){
        now=sta%mo;
        for (int i=hd[now];i;i=nxt[i])
        if (st[i]==sta)
            return ;
        
        cnt++;
        st[cnt]=sta;
        nxt[cnt]=hd[now];
        hd[now]=cnt;
    }

    inline void roll()
    {
        long long burning,status;
        REP(i,1,cnt)
        {
            burning=st[i]&BURN;
            status=st[i]>>(m+1);

            burning=(burning<<1)&BURN;
            status=(status*10);
            status-=(status/pw[m+1])*pw[m+1];

            st[i]=(status<<(m+1))|burning;
        }
    }
}h[2];

//u-1 r-2 d-4 l-8

void init()
{
    //RII(n,m);
 //m-=2;
 n=9;
    m=6;
    int x;
    RI(x);
    swap(n,m);

    x=m-x+1;
    REP(i,1,m)
    if (i!=x)
    {
        a[1][i][0]=1;
        a[1][i][1]=0;
    }
    else
    {
        a[1][i][0]=2;
        a[1][i][1]=1|4;
        a[1][i][2]=2|8;
    }
    n++;
    
    BURN=(1<<(m+1))-1;
    int ll,rr,dd,uu;
    char tt[12]={0};
    int tmp;
    REPD(j,m,1)
    {
        RS(tt+1);
    REP(i,2,n)
    {
        if (tt[i-1]=='.')tmp=0;
        else if (tt[i-1]=='L') tmp=3;
        else if (tt[i-1]=='T') tmp=7;
        else if (tt[i-1]=='-') tmp=5;
        else if (tt[i-1]=='+') tmp=15;
        debug("%d ",tmp);
        uu=(tmp&8)>0; 
        rr=(tmp&1)>0; 
        dd=(tmp&2)>0; 
        ll=(tmp&4)>0; 
        tmp=uu+rr+dd+ll;
        if(tmp<=1)
        {
            a[i][j][0]=1;
            a[i][j][1]=0;
        }
        else if (tmp==2)
        {
            if ( (uu && dd) || (ll && rr) )
            {
                a[i][j][0]=2;
                a[i][j][1]=1|4;
                a[i][j][2]=2|8;
            }
            else
            {
                a[i][j][0]=4;
                a[i][j][1]=1|2;
                a[i][j][2]=2|4;
                a[i][j][3]=4|8;
                a[i][j][4]=8|1;
            }
        }
        else if (tmp==3)
        {
            a[i][j][0]=4;
            a[i][j][1]=2|4|8;
            a[i][j][2]=1|4|8;
            a[i][j][3]=1|2|8;
            a[i][j][4]=1|2|4;
        }
        else
        {
            a[i][j][0]=1;
            a[i][j][1]=1|2|4|8;
        }
    }debug("\n");
    }
}

int L,R;
long long adq[MAXQ];

int b[MAXN];
int hshs[MAXN];
int c[MAXN];
int cc;

void decode(long long x){
    int len=0;
    MS(hshs,0);
    MS(b,0);
    while (x){
        b[len++]=x%10;
        hshs[x%10]=1;
        x/=10;
    }
}

long long encode(){
    long long ret=0;
    REPD(i,m,0)
    {
        ret*=10;
        ret+=b[i];
    }
    return ret;
}

int hamming_weight(int x){
    int ret=0;
    while (x)
    {
        ret++;
        x-=lowbit(x);
    }
    return ret;
}
// j-1 j

inline void watch(long long burning){
    debug("s:");REP(i,0,m) debug("%d",b[i]); debug(" ");
    debug("b:");REP(i,0,m) debug("%d",(burning&tw[i])>0); debug("\n");
}

int nxt=1,cur=0;

void dp()
{
    long long burning=0,status=0;
    long long mxburning,mxstatus;
    int mxplug=0,plug=0;
    int best=0;

    REP(i,1,m) burning+=tw[i]; 
    REP(i,1,m) status+=pw[i];
    h[cur].push((status<<(m+1))+burning);

    int x,y,z;

    int ll,rr,dd,uu;

    bool connected;
    bool burned;

    REP(i,1,n)
    {
        REP(j,1,m)
        {
            h[nxt].init();
            //debug("%d %d:",i,j);
         mxplug=plug=mxburning=best=0;
            
            L=R=0;
            //debug("%d\n",h[cur].cnt);
         REP(k,1,h[cur].cnt)
            {

                REP(aaa,1,a[i][j][0])
                {
                    plug=0;
                    burning=h[cur].st[k]&BURN;
                    if (!burning) continue;
                    status=h[cur].st[k]>>(m+1);

                    decode(status);
                // if (aaa==1) watch(burning);

                    x=b[j-1];
                    y=b[j];
                    z=1; while (hshs[z]) z++;

                    uu=a[i][j][aaa]&1;
                    rr=a[i][j][aaa]&2;
                    dd=a[i][j][aaa]&4;
                    ll=a[i][j][aaa]&8;

                    connected=(y && uu)||(x && ll);
                    burned=false;
                    if (y && uu)
                        if (burning&tw[j])
                            burned|=true;

                    if (x && ll)
                        if (burning&tw[j-1])
                            burned|=true;

                    if (connected)
                    {
                        if (x && ll) z=x;
                        else z=y;
                    }

                    if(x && y && uu && ll)
                    {
                        int nmn=min(x,y),nmx=max(x,y);
                        REP(i,0,m) if (b[i]==nmx) b[i]=nmn;
                        REP(i,0,m) if (b[i]>nmx) b[i]--;
                        if (burned)
                        REP(i,0,m) if (b[i]==nmn) burning|=tw[i];
                        z=nmn;
                    }

                    b[j-1]=b[j]=0;
                    if (burning&tw[j-1]) burning^=tw[j-1];
                    if (burning&tw[j]) burning^=tw[j];

                    if (dd)
                    {
                        b[j-1]=z;
                        if (burned) burning|=tw[j-1];
                    }

                    if (rr)
                    {
                        b[j]=z;
                        if (burned) burning|=tw[j];
                    }

                    //cut_1
                 if (!burning) continue;
                    //cut_2
                 MS(hshs,0);
                    REP(i,0,m)
                    {
                        hshs[b[i]]++;
                        if (b[i]) plug|=tw[i];
                    }
                    REP(i,0,m) 
                    if (b[i] && hshs[b[i]]==1 && (burning&tw[i])==0)
                    {
                        b[i]=0;
                        hshs[b[i]]=0;
                    }
                    
                    // min_exp
                 /*
                    cc=0;
                    MS(c,0);
                    REP(i,0,m) if (hshs[i]) c[i]=++cc;
                    REP(i,0,m) b[i]=c[b[i]]; 
                    */
                    
                    c[0]=0; REP(i,1,m) c[i]=m;
                    REP(i,1,m) c[b[i]]=min(c[b[i]],i);
                    REP(i,0,m) b[i]=c[b[i]];
                    
                    
                    status=encode();
                    adq[R++]=(status<<(m+1))+burning;
                    //cut_3
                 
                    int hmw=hamming_weight(burning);
                    
                    if (hmw>best)
                    {
                        best=hmw;
                        mxburning=burning;
                        mxstatus=status;
                        mxplug=plug;
                    }
                    /*else if (hmw==best && (mxplug&plug)==mxplug)
                    {
                        best=hmw;
                        mxburning=burning;
                        mxstatus=status;
                        mxplug=plug;
                    }*/
                }
            }

            if (L!=R)
                h[nxt].push((mxstatus<<(m+1))+mxburning);
        
            while (L!=R)
            {
                burning=adq[L]&BURN;
                status=adq[L]>>(1+m);
                decode(status);
                plug=0;
                REP(i,0,m) if (b[i]) plug|=tw[i];

                if ( !( ((burning&mxburning)==burning) && ((plug&mxplug)==plug)) )
                    h[nxt].push(adq[L]);

                L++;
            }

            cur^=1;
            nxt^=1;
        }
        h[cur].roll();
    }

    best=0;
    //debug("----------------------\n");
 MS(b,0);
    REP(i,1,h[cur].cnt){
        burning=h[cur].st[i]&BURN;
        //watch(burning);
     //if (hamming_weight(burning)>=best) watch(burning);
     best=max(best,hamming_weight(burning));
    }
    printf("%d\n",best);
}

int main()
{
    open();
    int _=0;
    pw[0]=1; REP(i,1,10) pw[i]=pw[i-1]*10;
    tw[0]=1; REP(i,1,10) tw[i]=tw[i-1]*2;
    init();
    dp();
    debug("%.3lf\n",sizeof(h)*1./1024/1024);
    close();
    return 0;
}

「樹形dp」
樹形dp一般難點在兩個地方。
1.設計合適的狀態
2.枚舉根的dp轉不枚舉根的dp。

「APIO2014 連珠線」
如果意識模糊的話,先寫個的dp吧。
先枚舉根。
考慮到藍色的路徑一定是許多x-y-z的形式,爺爺-父親-兒子。
此時我們枚舉當前點是否爲中間點。記錄dp[p][0/1]
其中dp[root][1]的最大值爲ans。
轉移很簡單。自己推一推。是
如何取消枚舉根?考慮記錄一下某顆子樹內除去某一個兒子的dp值,這樣就可以輕鬆把根轉移到兒子去了。
我的代碼略長。XD

「dp的优化」
1.斜率优化
2.四边形不等式优化
3.单调队列优化
4.数据结构优化
5.基于答案单调性的分治优化

「IOI 2014 Holiday」
考虑往一个方向dp得到花费d天到的最优决策点是哪里。
注意到决策点的单调性。
我们可以考虑分治求解,限制暴力查询最优决策点的范围。
这个的复杂度是
知道决策点以后就随便暴力了咯。

Recent Posts

comments powered by Disqus