您的位置: 首页 > IT文章 > 动态dp

动态dp

分类: IT文章 • 2024-03-05 17:31:22

---恢复内容开始---

　　谁知道这是一个什么鬼畜的东西反正我学了一下午。感觉不算很难是我蠢了。。。

我们从一到模板题开始吧。

动态dp

最大权独立集？？？貌似是一个和二分图有点关系的。其实就是让你求二分图的其中一张使其点权和最大。

这个不是没有上司的舞会么好简单啊！但是还带点权修改？貌似不太好了。

动态dp

nm暴力是60分诶。很不错。

//#incldue<bits/stdc++.h>
#include<iostream>
#include<queue>
#include<iomanip>
#include<cctype>
#include<cstdio>
#include<deque>
#include<utility>
#include<cmath>
#include<ctime>
#include<cstring>
#include<string>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#define INF 214748364
#define max(x,y) (x>y?x:y)
#define min(x,y) (x>y?y:x)
#define R register
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline int read()
{
    R int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void put(R int x)
{
    x<0?putchar('-'),x=-x:0;
    int num=0;char ch[50];
    while(x)ch[++num]=x%10+'0',x/=10;
    num==0?putchar('0'):0;
    while(num)putchar(ch[num--]);
    putchar('
');return;
}
//最大点权独立集问题
const int MAXN=1002;
int n,m,len;
int w[MAXN];
int lin[MAXN],nex[MAXN<<1],ver[MAXN<<1];
int f[MAXN][2],vis[MAXN];
inline void add(int x,int y)
{
    ver[++len]=y;
    nex[len]=lin[x];
    lin[x]=len;
}
inline void dp(int x)
{
    f[x][1]=w[x];f[x][0]=0;vis[x]=1;
    for(int i=lin[x];i;i=nex[i])
    {
        int tn=ver[i];
        if(vis[tn])continue;
        dp(tn);
        f[x][1]+=f[tn][0];
        f[x][0]+=max(f[tn][0],f[tn][1]);
    }
    return;
}
int main()
{
    //freopen("1.in","r",stdin);
    n=read();m=read();
    for(int i=1;i<=n;++i)w[i]=read();
    for(int i=1;i<n;++i)
    {
        int x,y;
        x=read();y=read();
        add(x,y);add(y,x);
    }
    for(int i=1;i<=m;++i)
    {
        int x,y;
        x=read();y=read();
        memset(vis,0,sizeof(vis));
        w[x]=y;dp(1);
        put(max(f[1][1],f[1][0]));
    }
    return 0;
}

View Code

下面是100分解法发现某个点的更改只和这个点到根的路径有关可以只更改其到根的路径即可。这样最坏还是nm的。

考虑树链刨分快速跳到根可是dp的过程怎么办考虑加速dp的过程即矩阵乘法加快dp

显然我们是可以列出一个矩阵为 [f0,f0] 转移到父亲时乘上父亲的 [g0',g0'] 得到父亲的dp值。

[f1,-INF] [g1',-INF]

这里的乘是广义的即相加取max 当然是符合结合律的，因为有人说的是max是符合结合律的加法也符合结合律所以这就满足了。

当然还有就是在floyd的时候我们发现是可以列出邻接矩阵然后进行矩阵乘法那时用的是相加取min 此时肯定也是符合的吧。书上说的是显然。

不妨我来证明一下吧: 我们想证明这个矩阵的具有结合律那要不就是3个矩阵的证明要不就是4个矩阵的证明，我用4个矩阵吧看起来更鲜明一点。

设有四个矩阵 a,b,c,d形如如上的矩阵此时 a*b*c*d=(a*b)*(c*d) 此时展开后得到的大矩阵的第一项为

max((max(a0+b0,a0+b1)+max(c0+d0,c0+d1)),a0+b0+c1+d0) 观察此时的第一项意思是第一项是不选择的那么就是我选不选第2项了，如果选择了第二项第三项是一定不能选的此时固定1 3 一定不选判断2 4 是否选择要不就是124 看一下是选择第3项是否会更优。发现这和我们单步乘的结果是一模一样的所以第一项是正确的我们看第一项的下方的一项。

为：(a1+b0+max(c0+d0,c0+d1),a1+b0+c1+d0) 解读一下这一项是要选a1的可见比max处都是有a1的有a1的话就是不能有b1那就是c和d谁选谁不选或者都不选的问题了，对于第一项来说我们固定c不选那就是b选或不选的了一下子满足上方两种条件选d 或者都不选至于第二项我们强制选c1 那就一定不能选择d1了成功解决了子问题。发现这也和原来的单步乘是一样的由于我们只是需求矩阵的这两项即可，对于其他位置我们不再赘述。

综上此矩阵具有结合律。得证.

发现这个矩阵有结合律之后我们可以使用线段树来维护这个性质树链刨分后我们保证了每一个点跳到根节点的步骤是有限的，所以我们维护重链的路径即可完成修改。修改之时我们只需从当前点调到当前链的顶端然后用顶端手动更新其父亲再次跳到顶端以此来保证复杂度。

写了7h 我算是服了。

//#incldue<bits/stdc++.h>
#include<iostream>
#include<queue>
#include<iomanip>
#include<cctype>
#include<cstdio>
#include<deque>
#include<utility>
#include<cmath>
#include<ctime>
#include<cstring>
#include<string>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#define INF 214748364888ll
#define max(x,y) (x>y?x:y)
#define min(x,y) (x>y?y:x)
#define ls p<<1
#define rs p<<1|1
#define ll long long
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void put(ll x)
{
    x<0?putchar('-'),x=-x:0;
    ll num=0;char ch[50];
    while(x)ch[++num]=x%10+'0',x/=10;
    num==0?putchar('0'):0;
    while(num)putchar(ch[num--]);
    putchar('
');return;
}
//最大点权独立集问题
const ll MAXN=100002;
ll n,m,len,cnt;
ll w[MAXN];
ll lin[MAXN],nex[MAXN<<1],ver[MAXN<<1];
ll fa[MAXN],sz[MAXN],top[MAXN],id[MAXN];
ll d[MAXN],son[MAXN],pos[MAXN],en[MAXN];
ll f[MAXN][2];
struct wy{ll a[2][2];}t[MAXN<<2],tmp[MAXN];
inline void add(ll x,ll y)
{
    ver[++len]=y;
    nex[len]=lin[x];
    lin[x]=len;
}
inline void dp(ll x,ll father)
{
    f[x][1]=w[x];f[x][0]=0;
    for(ll i=lin[x];i;i=nex[i])
    {
        ll tn=ver[i];
        if(tn==father)continue;
        dp(tn,x);
        f[x][1]+=f[tn][0];
        f[x][0]+=max(f[tn][0],f[tn][1]);
    }
    return;
}
inline void dfs(ll x,ll father)
{
    sz[x]=1;fa[x]=father;
    d[x]=d[father]+1;
    for(ll i=lin[x];i;i=nex[i])
    {
        ll tn=ver[i];
        if(tn==father)continue;
        dfs(tn,x);
        sz[x]=sz[x]+sz[tn];
        if(sz[son[x]]<sz[tn])son[x]=tn;
    }
}
inline void dfs1(ll x,ll father)
{
    top[x]=father;
    id[x]=++cnt;pos[cnt]=x;
    if(!son[x]){en[x]=x;return;}
    dfs1(son[x],father);en[x]=en[son[x]];
    for(ll i=lin[x];i;i=nex[i])
    {
        ll tn=ver[i];
        if(tn!=fa[x]&&tn!=son[x])
        dfs1(tn,tn);
    }
    return;
}
wy operator *(wy a,wy b)
{
    wy T;
    T.a[0][0]=max(a.a[0][0]+b.a[0][0],a.a[0][1]+b.a[1][0]);
    T.a[0][1]=max(a.a[0][0]+b.a[0][1],a.a[0][1]+b.a[1][1]);
    T.a[1][0]=max(a.a[1][0]+b.a[0][0],a.a[1][1]+b.a[1][0]);
    T.a[1][1]=max(a.a[1][0]+b.a[0][1],a.a[1][1]+b.a[1][1]);
    return T;
}
inline void build(ll p,ll l,ll r)
{
    if(l==r)
    {
        ll f1=w[pos[l]],f0=0;
        for(ll i=lin[pos[l]];i;i=nex[i])
        {
            ll tn=ver[i];
            if(tn!=fa[pos[l]]&&tn!=son[pos[l]])
                f1+=f[tn][0],f0+=max(f[tn][0],f[tn][1]);
        }
        //cout<<f0<<' '<<f1<<endl;
        t[p].a[0][0]=f0;t[p].a[0][1]=f0;
        t[p].a[1][0]=f1;t[p].a[1][1]=-INF;
        tmp[l]=t[p];return;
    }
    ll mid=(l+r)>>1;
    build(ls,l,mid);build(rs,mid+1,r);
    t[p]=t[ls]*t[rs];return;
}
inline wy ask(ll p,ll l,ll r,ll L,ll R)
{
    if(L==l&&R==r)return t[p];
    ll mid=(l+r)>>1;
    if(R<=mid)return ask(ls,l,mid,L,R);
    if(L>mid)return ask(rs,mid+1,r,L,R);
    return ask(ls,l,mid,L,mid)*ask(rs,mid+1,r,mid+1,R);
}
inline void modify(ll p,ll l,ll r,ll x)
{
    if(l==r){t[p]=tmp[l];return;}
    ll mid=(l+r)>>1;
    if(x<=mid)modify(ls,l,mid,x);
    else modify(rs,mid+1,r,x);
    t[p]=t[ls]*t[rs];
    return;
}
void modify(ll u,ll k)
{
    tmp[id[u]].a[1][0]+=k-w[u],w[u]=k;
    //cout<<top[u]<<endl;
    while(u)
    {
        wy a=ask(1,1,n,id[top[u]],id[en[u]]);
        //if(w==-75)cout<<a.a[0][0]<<' '<<id[top[u]]<<' '<<id[en[u]]<<' '<<id[u]<<endl;
        modify(1,1,n,id[u]);
        wy b=ask(1,1,n,id[top[u]],id[en[u]]);
        u=fa[top[u]];if(!u)break;
        //if(w==-75)cout<<u<<endl;
        tmp[id[u]].a[0][1]=(tmp[id[u]].a[0][0]+=max(b.a[0][0],b.a[1][0])-max(a.a[0][0],a.a[1][0]));
        tmp[id[u]].a[1][0]+=b.a[0][0]-a.a[0][0];
        //tmp[id[u]].a[1][0]=(tmp[id[u]].a[0][0]+=max(b.a[0][0],b.a[0][1])-max(a.a[0][0],a.a[0][1]));//
        //tmp[id[x]].a[0][0]=(tmp[id[x]].a[1][0]+=max(b.a[0][0]-a.a[0][0],b.a[0][1]-a.a[0][1]));//
        //tmp[id[u]].a[0][1]+=b.a[0][0]-a.a[0][0];//tmp[id[x]].a[1][1]=-INF;
    }
}
int main()
{
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    n=read();m=read();
    for(ll i=1;i<=n;++i)w[i]=read();
    for(ll i=1;i<n;++i)
    {
        ll x,y;
        x=read();y=read();
        add(x,y);add(y,x);
    }
    dfs(1,0);dp(1,0);dfs1(1,1);
    //for(ll i=1;i<=n;++i)put(en[i]);
    build(1,1,n);
    //cout<<t[1].a[0][0]<<endl;
    for(ll i=1;i<=m;++i)
    {
        ll x,y;
        //if(i==2)cout<<id[1]<<' '<<id[en[1]]<<endl;
        x=read();y=read();
        modify(x,y);
        wy a=ask(1,1,n,id[1],id[en[1]]);
        put(max(a.a[0][0],a.a[1][0]));
    }
    return 0;
}

View Code

动态dp

仔细读题发现和上面的一道题近乎一模一样关键困难的是列出一个矩阵然后此时针对每一个询问如果强制不能建军那就给它的权值加上INF

如果可以建军那么给它的权值减去INF 记得最后得到的答案先取min 再加上刚刚的偏移量保证依照题目的意思。

又写了7h 自闭了.

//#incldue<bits/stdc++.h>
#include<iostream>
#include<queue>
#include<iomanip>
#include<cctype>
#include<cstdio>
#include<deque>
#include<utility>
#include<cmath>
#include<ctime>
#include<cstring>
#include<string>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
#define INF 1000000000000000ll
#define ll long long
#define ls p<<1
#define rs p<<1|1
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void put(ll x)
{
    x<0?putchar('-'),x=-x:0;
    ll num=0;char ch[50];
    while(x)ch[++num]=x%10+'0',x/=10;
    num==0?putchar('0'):0;
    while(num)putchar(ch[num--]);
    putchar('
');return;
}
const int MAXN=100010;
int n,m,len,cnt;
int lin[MAXN],nex[MAXN<<1],ver[MAXN<<1];
int sz[MAXN],fa[MAXN],top[MAXN],son[MAXN];
int bot[MAXN],id[MAXN],pos[MAXN];
ll f[MAXN][2],v[MAXN];
char ch[5];
struct wy
{
    ll a[2][2];
    wy(){a[0][0]=a[1][0]=a[0][1]=a[1][1]=INF;}
}t[MAXN<<2],tmp[MAXN];
inline void add(int x,int y)
{
    ver[++len]=y;
    nex[len]=lin[x];
    lin[x]=len;
}
inline void dfs(int x,int father)
{
    fa[x]=father;
    f[x][0]=0;f[x][1]=v[x];
    sz[x]=1;
    for(int i=lin[x];i;i=nex[i])
    {
        int tn=ver[i];
        if(tn==father)continue;
        dfs(tn,x);
        sz[x]+=sz[tn];
        f[x][1]+=min(f[tn][0],f[tn][1]);
        f[x][0]+=f[tn][1];
        if(sz[son[x]]<sz[tn])son[x]=tn;
    }
}
inline void dp(int x,int father)
{
    top[x]=father;
    id[x]=++cnt;
    pos[cnt]=x;
    if(!son[x]){bot[x]=x;return;}
    dp(son[x],father);bot[x]=bot[son[x]];
    for(int i=lin[x];i;i=nex[i])
    {
        int tn=ver[i];
        if(tn!=fa[x]&&tn!=son[x])dp(tn,tn);
    }
    return;
}
wy operator*(wy a,wy b)
{
    wy T;
    T.a[0][0]=min(a.a[0][0]+b.a[0][0],a.a[0][1]+b.a[1][0]);
    T.a[0][1]=min(a.a[0][0]+b.a[0][1],a.a[0][1]+b.a[1][1]);
    T.a[1][0]=min(a.a[1][0]+b.a[0][0],a.a[1][1]+b.a[1][0]);
    T.a[1][1]=min(a.a[1][0]+b.a[0][1],a.a[1][1]+b.a[1][1]);
    return T;
}
inline void build(int p,int l,int r)
{
    if(l==r)
    {
        int x=pos[l];
        ll g0=0,g1=v[x];
        for(int i=lin[x];i;i=nex[i])
        {
            int tn=ver[i];
            if(tn!=fa[x]&&tn!=son[x])
                g0+=f[tn][1],g1+=min(f[tn][0],f[tn][1]);
        }
        t[p].a[0][0]=t[p].a[0][1]=g1;
        t[p].a[1][0]=g0;t[p].a[1][1]=INF;
        tmp[l]=t[p];
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    t[p]=t[ls]*t[rs];
    return;
}
inline wy ask(int p,int l,int r,int L,int R)
{
    if(L<=l&&R>=r)return t[p];
    int mid=(l+r)>>1;
    if(L>mid)return ask(rs,mid+1,r,L,R);
    if(R<=mid)return ask(ls,l,mid,L,R);
    return ask(ls,l,mid,L,R)*ask(rs,mid+1,r,L,R);
}
inline void modify(int p,int l,int r,int x)
{
    if(l==r){t[p]=tmp[l];return;}
    int mid=(l+r)>>1;
    if(x<=mid)modify(ls,l,mid,x);
    else modify(rs,mid+1,r,x);
    t[p]=t[ls]*t[rs];
}
inline void modify(int x,ll w)
{
    tmp[id[x]].a[0][0]=tmp[id[x]].a[0][1]+=w-v[x];v[x]=w;
    while(x)
    {
        wy a=ask(1,1,n,id[top[x]],id[bot[x]]);
        modify(1,1,n,id[x]);
        wy b=ask(1,1,n,id[top[x]],id[bot[x]]);
        x=fa[top[x]];if(!x)break;
        tmp[id[x]].a[0][0]=tmp[id[x]].a[0][1]+=min(b.a[0][0],b.a[1][0])-min(a.a[0][0],a.a[1][0]);
        tmp[id[x]].a[1][0]+=b.a[0][0]-a.a[0][0];
    }
    return;
}
int main()
{
    //freopen("1.in","r",stdin);
    n=read();m=read();scanf("%s",ch+1);
    for(int i=1;i<=n;++i)v[i]=read();
    for(int i=1;i<n;++i)
    {
        int x,y;
        x=read();y=read();
        add(x,y);add(y,x);
    }
    dfs(1,0);dp(1,1);
    build(1,1,n);
    //wy ans=ask(1,1,n,id[1],id[bot[1]]);put(min(ans.a[0][0],ans.a[1][0]));
    for(int i=1;i<=m;++i)
    {
        int a,b,a1,b1;
        a=read();a1=read();b=read();b1=read();
        if(a1==0&&b1==0&&(fa[a]==b||fa[b]==a)){puts("-1");continue;}
        ll va=v[a],vb=v[b],sum=0,s;
        if(!a1)modify(a,INF+va);else modify(a,va-INF),sum+=INF;
        if(!b1)modify(b,INF+vb);else modify(b,vb-INF),sum+=INF;
        wy ans=ask(1,1,n,id[1],id[bot[1]]);
        s=min(ans.a[0][0],ans.a[1][0])+sum;
        put(s);
        modify(a,va);modify(b,vb);
    }
    return 0;
}

View Code

动态dp

相关推荐