精华内容
下载资源
问答
  • 常见的DP优化类型总结
  • dp优化模板(征途)

    2020-04-15 11:18:58
    dp优化算法模板..
  • HDU gems gems gems [DP+DP优化]

    题意:给你长度为n的数列,两个人从左往右轮流取数,假设上一个人取k个,当前这个人只能选择从左往右取k个或k+1个,初始k为0,Alice希望她拿的数量减去Bob拿的数量差值要大,Bob希望差值要小,问最后剩下多少。

    题解:首先我们考虑设dp[i][k][j]表示当前第j个人在i的位置上取k个的时候的差值。

    对于Alice:dp[i][k][0]=min(dp[i+k][k][1],dp[i+k][k+1][1])+(sum[i+k-1]-sum[i-1])

    对于Bob:dp[i][k][1]=max(dp[i+k][k][0],dp[i+k][k+1][0])-(sum[i+k-1]-sum[i-1])

    但这道题卡空间,所以我们先考虑一个种优化,由于k是+1的增长,所以k最多是sqrt(2*n)+1,不超过200。

    但是这样还不够,所以我们再考虑pos,由于pos的转移只需要后pos+k个,所以我们用滚动数字,将第一维优化为255的空间。

    AC代码:

    #include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<algorithm>
    #define mod 255
    using namespace std;
    int dp[255][205][2];
    int a[20005];
    int sum[20005];
    int main()
    {
    	int T;
    	scanf("%d",&T);
    	while(T--)
    	{
    		memset(dp,0,sizeof(dp));
    		int n;
    		scanf("%d",&n);
    		for(int i=1;i<=n;i++)
    		{
    			scanf("%d",&a[i]);
    			sum[i]=sum[i-1]+a[i];
    		}
    		if(n==1)
    		{
    			printf("%d\n",a[1]);
    			continue;
    		}
    		for(int i=n;i>0;i--)
    			for(int k=min(n-i+1,(int)sqrt(2*i)+1);k>=1;k--)
    			{
    				if(i+2*k-1<=n)
    				{
    					dp[i%mod][k][0]=dp[(i+k)%mod][k][1];
    					dp[i%mod][k][1]=dp[(i+k)%mod][k][0];
    					if(i+2*k<=n)
    					{
    						dp[i%mod][k][0]=min(dp[i%mod][k][0],dp[(i+k)%mod][k+1][1]);
    						dp[i%mod][k][1]=max(dp[i%mod][k][1],dp[(i+k)%mod][k+1][0]);
    					}
    						
    				}
    				dp[i%mod][k][0]+=sum[i+k-1]-sum[i-1];
    				dp[i%mod][k][1]-=sum[i+k-1]-sum[i-1];
    			}
    		printf("%d\n",max(dp[1][1][0],dp[1][2][0]));
    	}
    }

    实际上还可以优化第三维,因为Alice希望差值尽可能大,Bob希望差值尽可能小,所以相当于每个人都希望自己手上的数字更大。

    AC代码:

    #include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<algorithm>
    #define mod 205
    using namespace std;
    int dp[205][205];
    int sum[20005];
    int main()
    {
    	int T,k;
    	scanf("%d",&T);
    	while(T--)
    	{
    		memset(dp,0,sizeof(dp));
    		int n,i,k;
    		scanf("%d",&n);
    		for(int i=1;i<=n;i++)
    		{
    			scanf("%d",&k);
    			sum[i]=sum[i-1]+k;
    		}
    		if(n==1)
    		{
    			printf("%d\n",sum[1]);
    			continue;
    		}
    		for(i=n;i>0;i--)
    			for(k=min(n-i+1,(int)sqrt(2*i)+1);k>=1;k--)
    			{
    				if(i+2*k-1<=n)
    				{
    					dp[i%mod][k]=-dp[(i+k)%mod][k];
    					if(i+2*k<=n)dp[i%mod][k]=min(dp[i%mod][k],-dp[(i+k)%mod][k+1]);
    				}
    				dp[i%mod][k]+=sum[i+k-1]-sum[i-1];
    			}
    		printf("%d\n",max(dp[1][1],dp[1][2]));
    	}
    }


    展开全文
  • DP优化总结

    千次阅读 2017-09-05 08:32:19
    矩阵优化DP 例子 fib数列 fib数列拓展 kmp转移 小型图的转移 决策单调栈优化 例子 玩具装箱Toy 土地购买 单调队列优化DP 例子 单调队列维护决策 单调队列维护可选决策 基环外向树的直径 矩阵...

    矩阵优化DP

    满足三个特点:
    1.转移要选取的决策较少。(一般在常数级别)
    2.转移的步骤很多。(一般是1e10以上的级别)
    3.每一步的转移方程一样。(和递推类似)

    *一般满足转移方程:

    an+m=i=0m1an+ibi

    例子:

    fib数列

    一般转移方程为 f(n)=f(n1)+f(n2) ,决策只有两个,转移步骤一般很大,且每次转移都一样,满足优化条件。
    不放设矩阵

    A=[f(n1),f(n)]

    每次要得到另一个矩阵

    B=[f(n),f(n1)+f(n)]

    转移矩阵已经很明显:

    AT=B,T=[0111]

    显然, Bn=A1Tn1 。而矩阵满足快速幂。可在 O(m3logn) 时间内解决。(m是每次转移决策数,此时m=2)。

    fib数列拓展:

    1. f(n)=f(n2)+f(n1)+1

    转移

    [f(n1),f(n),1][f(n),f(n1)+f(n)+1,1]

    转移矩阵

    T=010110001 .

    时间复杂度 O(33logn)

    2. f(n)=f(n2)+f(n1)+n+1,s(n)f(n)s(n)

    转移

    [f(n1),f(n),n+1,1,s(n)][f(n),f(n1)+f(n)+n+2,n+2,1,s(n)+f(n+1)]

    转移矩阵

    T=0100111111001110001100001

    时间复杂度 O(53logn)

    kmp转移

    “GT考试”题解

    小型图的转移

    “迷路”题解

    决策单调栈优化

    如果转移满足两个特点:
    1.转移方程: f(x)=mini=1x1f(i)+w[i,x] (w[i,x]) 为i,x转移的代价(已知条件)。
    2. w 函数满足w[i,j]+w[i1,j1]w[i,j1]+w[i,j1](i<i1,j<j1)

    那么称这个转移满足决策单调性: g(x)=k 表示 mini=1x1f(i)+w[i,x] k 处取得,那么ij,s.t.g(i)g(j)

    w 函数的性质一般难以观察,只用打表检验g(x)的性质即可。

    考虑优化:
    1. i g(x1)开始枚举。
    有时候可以达到 O(n) 的线性复杂度,但是如果 g(i)=1 则退化为 O(n2)

    2. g(k) 单调递增,对于每一个 f(i) ,二分更新后面的g(k)(决策使用单调栈)。
    严格 O(nlogn)

    例子

    玩具装箱Toy

    题意:
    n 个玩具,要将它们分为若干组进行打包,每个玩具有一个长度len[x]。每一组必须是连续的一组玩具。如果将第 x 到第y个玩具打包到一组,那么它们的长度 l=ji1+k=ijlen[k] ,将这组玩具打包所需的代价等于 (lL)2 。问将所有玩具打包的最小代价是多少。注意到每组玩具个数并没有限制。 n<=50000

    题解:
    打表观察到决策单调性后直接二分解决。这里贴一份代码:

    #include<bits/stdc++.h>
    using namespace std;
    typedef pair<int,int> pii;
    typedef long long ll;
    streambuf *ib,*ob;
    inline int read()
    {
        char ch=ib->sbumpc();int i=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=ib->sbumpc();}
        while(isdigit(ch)){i=(i<<1)+(i<<3)+ch-'0';ch=ib->sbumpc();}
        return i*f;
    }
    int buf[80];
    inline void W(ll x)
    {
        if(!x){ob->sputc('-');return;}
        if(x<0){ob->sputc('-');x=-x;}
        while(x){buf[++buf[0]]=x%10,x/=10;}
        while(buf[0])ob->sputc(buf[buf[0]--]+'0');
    }
    
    const int Maxn=5e4+50;
    int n,head,tail;
    ll len[Maxn],L,f[Maxn];
    pii q[Maxn];
    inline ll calc(int i,int j){return (j-i+len[j]-len[i-1]-L)*(j-i+len[j]-len[i-1]-L);}
    inline int solve(int o,int now,int l,int r)
    {
        int ans=0;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(f[o]+calc(o+1,mid)>=f[now]+calc(now+1,mid))ans=mid,r=mid-1;
            else l=mid+1;
        }
        return ans;
    }
    int main()
    {
        ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);ib=cin.rdbuf();ob=cout.rdbuf();
        n=read(),L=read();
        for(int i=1;i<=n;i++)len[i]=1ll*read()+len[i-1];
        q[head=tail=1]=make_pair(1,0);
        for(int i=1;i<=n;i++)
        {
            f[i]=f[q[head].second]+calc(q[head].second+1,i);
            ((++q[head].first)>=q[head+1].first&&tail>head)?(head++):0;
            int pos=n;
            while(tail>=head&&(f[i]+calc(i+1,q[tail].first)<=f[q[tail].second]+calc(q[tail].second+1,q[tail].first)))pos=q[tail].first,tail--;
            if(tail<head)q[++tail]=make_pair(i+1,i);
            else
            {
                pos=solve(q[tail].second,i,q[tail].first,pos);
                if(pos)q[++tail]=make_pair(pos,i);
            }
        }
        W(f[n]);ob->sputc('\n');
    } 

    土地购买

    题意:
    n 块土地需要购买,每块土地都是长方形的,有特定的长与宽。你可以 一次性购买一组土地,价格是这组土地中长的最大值乘以宽的最大值。比方说一块5*3 的土地和一块9*2的土地在一起购买的价格就是 9*3。最小化买下所有的土地的费用。

    题解:
    显然对于长宽都含于另一个长方体的长方体可以忽略。
    那么剩下的长方体排布形式一定为:

    ij,s.t.xi<xj,yi>yj
    又有转移方程: f(i)=mink=0i1f(k)+w[k,i] ,其中 w[k,i]=yk·xi ,那么四边形不等式就很好证了:

    x4·y1+x3·y2x4·y2+x3·y1 (下标表示大小关系,x随i递减,y随j递增)

    因为: x4(y1y2)x3(y1y2) 得证。
    满足决策单调性。

    单调队列优化DP

    如果转移满足以下模型:
    f(x)=mini=b[x]x1g(i)+w[x](g(i)iw[x]x,b[x]x)

    那么可以用单调队列维护决策表达到 O(n) 的时间复杂度。

    怎么维护?
    发现对于一个决策 g(i) 只会影响到一定的 f(x) ,且越靠后面的 g(i) 影响的 f(x) 也越靠后面(因为b[x]随x不降)。那么一个决策如果比前面的决策更优,前面的决策就可以直接丢掉。(后面能够被丢掉决策更新的状态一定能被更优的该决策更新)。每次取队首元素,均摊 O(1)

    例子

    单调队列维护决策

    “生产商品”题解

    单调队列维护可选决策

    *这类dp满足可选决策时单调的,但最优决策要在可选决策中选取最优值,一般用set或平衡树(Splay\Treap)维护.
    如:
    poj3017:Cut the Sequence

    •问题描述

    给定一个有n个非负整数的数列a,要求将其划分为若干个部分,使得每部分的和不超过给定的常数m,并且所有部分的最大值的和最小。其中n<=105。
    例:n=8, m=17,8个数分别为2 2 2 | 8 1 8 |1 2,答案为12,分割方案如图所示。

    •解法分析

    刚开始拿到这道题目,首先要读好题:最大值的和最小。
    首先设计出一个动态规划的方法

    f[i]=maxj=b[x]i1{f[j]+Maxnumber[j+1,i]}

    其中 f[i] 代表把前i个数分割开来的最小代价。 b[i]=min(j|sum[j+1,i]m) 可以 O(n) 实现。
    直接求解复杂度最坏情况下( M 超大)是O(n2)的,优化势在必行。

    几个性质

    通过仔细观察,可以发现以下几点性质:
    ① 在计算状态 f(x) 的时候,如果一个决策k作为该状态的决策,那么可以发现第 k 个元素和第x个元素是不分在一组的。
    b[x] 随着 x 单调不降的,用这一点,可以想到什么?可以想到前面单调队列的一个限制条件。
    ③ 来看一个最重要的性质:如果一个决策k能够成为状态 f(x) 的最优决策,当且仅当 a[k]>a[j],j[k+1,x] 。为什么呢?其实证明非常非常容易(用到性质1),交给读者自己考虑。

    单调队列优化可选决策

    到此为止,我们可以这样做:由于性质三,每计算一个状态 f(x) ,它的有效决策集肯定是一个元素值单调递减的序列,我们可以像单调队列那样每次在队首删除元素,直到队首在数列中的位置小于等于 ,然后将a[x]插入队尾,保持队列的元素单调性。

    这时候问题来了,队首元素一定是最佳决策点吗?我们只保证了他的元素值最大……如果扫一遍队列,只是常数上的优化,一个递减序足以将它否决。

    我们观察整个操作,将队列不断插入、不断删除。对于除了队尾的元素之外,每个队列中的元素供当前要计算的状态的“值”是 f(q[x].position)+a[q[x+1].position] ,其中, q[x] 代表第x个队列元素, position 这代表他在原来数组中的位置,我们不妨把这个值记为 t 。那每一次在队首、队尾的删除就相当于删除t,每一次删除完毕之后又要插入一个新的 t ,然后需要求出队列中的t的最小值。

    我们发现,完成上述一系列工作的最佳选择就是平衡树,这样每个元素都插入、删除、查找各一遍,复杂度为O(logn),最后的时间复杂度是 O(nlogn)

    基环外向树的直径

    例如:bzoj1791:Island
    (这道题是真的难写。。)

    首先,每一个基环外向树相当于一个环上有一些点挂了一颗子树,先把这个点的深度算出来,再考虑环上做DP的方法:

    断开任意一条环边,再把这个环复制一遍,做 b[x]=xn+1 的dp就好了。
    给一份代码,可以参考参考

    #include<bits/stdc++.h>
    using namespace std;
    namespace IO
    {
        streambuf *ib,*ob;
        int buf[50];
        inline void init()
        {
            ios::sync_with_stdio(false);
            cin.tie(NULL);cout.tie(NULL);
            ib=cin.rdbuf();ob=cout.rdbuf();
        }
        inline int read()
        {
            char ch=ib->sbumpc();int i=0,f=1;
            while(!isdigit(ch)){if(ch=='-')f=-1;ch=ib->sbumpc();}
            while(isdigit(ch)){i=(i<<1)+(i<<3)+ch-'0';ch=ib->sbumpc();}
            return i*f;
        }
        inline void W(long long x)
        {
            if(!x){ob->sputc('0');return;}
            if(x<0){ob->sputc('-');x=-x;}
            while(x){buf[++buf[0]]=x%10;x/=10;}
            while(buf[0])ob->sputc(buf[buf[0]--]+'0');
        }
    }
    
    typedef long long ll;
    typedef pair<int,ll> pil;
    typedef pair<int,int> pii;
    const int Maxn=1e6+50;
    int n,ecnt=1,tail,tailtmp,bz,bg,last[Maxn],from[Maxn],vis[Maxn],ins[Maxn],id[Maxn];
    ll dp[Maxn][2],ans,res;
    pii statmp[Maxn];
    pil sta[Maxn];
    struct E{int to,val,nxt;}edge[Maxn*2];
    inline void add(int x,int y,int z)
    {
        edge[++ecnt].to=y;edge[ecnt].nxt=last[x];last[x]=ecnt;edge[ecnt].val=z;
        edge[++ecnt].to=x;edge[ecnt].nxt=last[y];last[y]=ecnt;edge[ecnt].val=z;
    }
    inline void dfs(int now,int val)
    {
        vis[now]=1;statmp[++tailtmp]=make_pair(now,val);id[now]=tailtmp;
        for(int e=last[now];e;e=edge[e].nxt)
        {
            int v=edge[e].to;
            if((e^1)==from[now])continue;
            if(!vis[v])from[v]=e,dfs(v,edge[e].val);
            else {statmp[id[v]].second=edge[e].val;bz=1;bg=id[v];return;}
            if(bz)return;
        }
        tailtmp--;
    }
    inline void dfs2(int now,int f=0)
    {
        vis[now]=1;
        for(int e=last[now];e;e=edge[e].nxt)
        {
            int v=edge[e].to;
            if(ins[v]||v==f)continue;
            dfs2(v,now);
            ll t=dp[v][0]+edge[e].val;
            if(t>=dp[now][0])dp[now][1]=dp[now][0],dp[now][0]=t;
            else if(t>dp[now][1])dp[now][1]=t;
            ans=max(ans,dp[now][1]+dp[now][0]);
        }
    }
    
    pil q[Maxn*2];
    int qhead,qtail;
    inline ll calc(int i)
    {
        for(int i=bg;i<=tailtmp;i++)sta[++tail]=statmp[i],ins[sta[tail].first]=1;
        for(int i=1;i<=tail;i++)dfs2(sta[i].first);
        memcpy(sta+tail+1,sta+1,sizeof(pil)*tail);int len=tail*2;
        for(int i=1;i<=len;i++)sta[i].second+=sta[i-1].second;
        ans=max(ans,dp[sta[1].first][0]);q[qhead=qtail=1]=make_pair(1,dp[sta[1].first][0]-sta[1].second);
        for(int i=2;i<=len;i++)
        {
            int lim=i-tail+1;
            while(q[qhead].first<lim)
            qhead++;
            ll t=dp[sta[i].first][0]+q[qhead].second+sta[i].second;
            ans=max(ans,t);
            t=dp[sta[i].first][0]-sta[i].second;
            while(qhead<=qtail&&q[qtail].second<=t)qtail--;
            q[++qtail]=make_pair(i,t);
        }
        return ans;
    }
    
    int main()
    {
        IO::init();n=IO::read();
        for(int i=1;i<=n;i++)
        {
            int y=IO::read(),z=IO::read();
            add(i,y,z);
        }
        for(int i=1;i<=n;i++)
        {
            if(!vis[i])
            {
                tailtmp=bg=bz=tail=ans=0;
                dfs(i,0);
                res+=calc(i);
            }
        }
        IO::W(res);IO::ob->sputc('\n');
    }

    多重背包的 (Onm) 优化

    首先,多重背包的转移方程是:

    f[i][x]=maxs[i]k=0{f[i1][xkc[i]]+kw[i]}

    如果决策连续就是裸的单调队列。现在考虑不连续:
    首先可以发现一个 x 只会取与它模c[i]相同的状态,那么在模意义下分别DP就好了。

        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<c[i];j++)
            {
                q[head=tail=1]=make_pair(f[j],0);
                for(int k=j+c[i];k<=m;k+=c[i])
                {
                    int a=k/c[i],t=f[k]-a*w[i];
                    while(head<=tail&&q[tail].first<=t)tail--;
                    q[++tail]=make_pair(t,a);
                    while(head<=tail&&q[head].second+s[i]<a)head++;
                    f[k]=max(f[k],q[head].first+a*w[i]);
                }
            }
        }

    斜率优化

    模型:

    f[i]=minj=1i1{a[i]g(j)+b[i]h(j)}

    这个模型写的比较抽象, 其实它的涵盖范围是很广的。 首先, a[i], b[i]不一定要是常量, 只要他们与决策无关, 都可以接受; 另外, g(j)和 h(j)不管是常量还是变量都没有关系, 只要他们是一个由i决定的二元组就可以了。

    为了方便描述, 把这个模型做如下转化:

    P=f[i],x=g(j),y=h(j)y=abx+Pb

    可以发现,状态现在就是许多条直线,而我们的任务是选出一条直线,使它经过前面出现的某一点,且的纵截距最小。 可以想象有一组斜率相同的直线自负无穷向上平移, 所碰到的第一个数据点就是最优决策。

    这个时候, 有一个重要的性质, 那就是: 所有最优决策点都在平面点集的凸包上

    基于这个事实, 我们可以开发出很多令人满意的算法。
    这时, 根据直线斜率与数据点分布的特征, 可以划分为两种情况:

    1.决策直线的斜率与二元组的横坐标同时满足单调性。

    这样的模型是比较好处理的, 因为这个时候由于斜率变化是单调的, 所以决策点必然在凸壳上单调移动。我们只需要维护一个单调队列和一个决策指针,每次决策时作这样几件事:

    1.决策指针( 也就是队首) 后移, 直至最佳决策点。
    2.进行决策。
    3.将进行决策之后的新状态的二元组加入队尾, 同时作 GrahamScan 式的更新操作维护凸壳。
    算法的时间复杂度为 O(n)

    例题

    土地购买

    再来观察这个转移方程:

    f[i]=minj=1i1{f[j]+x[i]y[j+1]}

    转化后:
    f[j]=x[i]y[j+1]+f[i]

    很明显,斜率 x[i] 单调递减, y[j+1] 单调递减,满足条件。上斜率优化就行了。

    #include<iostream>
    #include<cmath>
    #include<algorithm>
    #include<cstdio>
    using namespace std;
    const int Maxn=5e4+50;
    streambuf *ib,*ob;
    typedef long long ll;
    inline void init()
    {
        ios::sync_with_stdio(false);
        cin.tie(NULL);cout.tie(NULL);
        ib=cin.rdbuf();ob=cout.rdbuf();
    }
    inline int read()
    {
        char ch=ib->sbumpc();int i=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=ib->sbumpc();}
        while(isdigit(ch)){i=(i<<1)+(i<<3)+ch-'0';ch=ib->sbumpc();}
        return i*f;
    }
    int buf[50];
    inline void W(ll x)
    {
        if(!x){ob->sputc('0');return;}
        if(x<0){ob->sputc('-');x=-x;}
        while(x)buf[++buf[0]]=x%10,x/=10;
        while(buf[0])ob->sputc(buf[buf[0]--]+'0');
    }
    struct point
    {
        ll x,y;
        point(ll x=0,ll y=0):x(x),y(y){}
        friend inline point operator -(const point &a,const point &b)
        {
            return point(a.x-b.x,a.y-b.y);
        }
        friend inline ll dot(const point &a,const point &b)
        {
            return a.x*b.y-a.y*b.x;
        }
    }p[Maxn],q[Maxn];
    
    int n,tot,head,tail;
    ll f[Maxn];
    inline bool comp(const point &a,const point &b)
    {
        return a.y>b.y||(a.y==b.y&&a.x>b.x);
    }
    inline ll calc(int pos,int x)
    {
        return q[pos].y+p[x].x*q[pos].x;
    }
    int main()
    {
        init();
        n=read();
        for(int i=1;i<=n;i++)
        {
            int x=read(),y=read();
            p[i]=point(x,y);
        }
        sort(p+1,p+n+1,comp);
        int mx=p[tot=1].x;
        for(int i=2;i<=n;i++)
        {
            if(p[i].x<=mx)continue;
            p[++tot]=p[i];mx=p[i].x;
        }
        q[head=tail=1]=point(p[1].y,0);
        for(int i=1;i<=tot;i++)
        {
            while(head<tail&&calc(head,i)>=calc(head+1,i))head++;
            f[i]=calc(head,i);
            while(tail>=2&&dot(point(p[i+1].y,f[i])-q[tail-1],q[tail]-q[tail-1])<=0)tail--;
            q[++tail]=point(p[i+1].y,f[i]);
            if(head>tail)head=tail;
        }
        W(f[tot]);ob->sputc('\n');
    }

    玩具装箱Toy

    转移方程:

    f[i]=minj=1i1{f[j]+(ij1+sum[i]sum[j]L)2}[i]=i+sum[i]L1,b[j]=sum[j]+jf[i]=f[j]+(a[i]b[j])2f[i]a[i]2=(f[j]+b[j]2)2(a[i]b[j])

    x=b[j],y=f[j]+b[j]2 ,显然 2a[i] 单调增, x 单调增,可以上板了。

    仓库建设

    设所有前面的仓库转移到该仓库花费费用为Dilivercost[i],前面仓库的容量总和为 Sum[i] ,该仓库距离为 i ,建造所花费用Buildcost[i]。那么有转移:

    f[i]=minj=0i1{f[j]+Dilivercost[i]Dilivercost[j](Sum[j](dis[i]dis[j]))+Buildcost[i]}

    x=sum[j],y=f[j]Dilivercost[j]+sum[j]dis[j] 不难发现 x 单调递增。
    又有:
    f[i]=min{ydis[i]x}+Buildcost[i]+Dilivercost[i]

    dis[i] 也满足单增,可以套板了。

    特别行动队

    同样写出来可以斜率优化。
    (a只有小于0维护上凸包,若a大于0则维护下凸包)

    不满足斜率单调性

    这个没什么好说,用平衡树维护,做到 nlogn (CDQ分治也可以做)

    货币兑换Cash

    转移方程

    f[i]=max{f[i1],maxj=1i1{A[i]x[i]+B[i]y[i]}}

    不满足单调,一般两种解法:
    1.CDQ分治,保证处理完左边之后维护左半凸包并处理右边:http://paste.ubuntu.com/25699099/

    2.set(平衡树)维护凸包,当然这种操作没有CDQ简便,最好写CDQ.:http://paste.ubuntu.com/25699108/

    展开全文
  • DP 优化系列

    千次阅读 2012-08-22 11:19:54
    国家集训队论文中有大量关于DP优化的论文:毛子青的《动态规划算法的优化技巧》、朱晨光的《从《鹰蛋》一题浅析对动态规划算法的优化》、杨哲的《凸完全单调性的一个加强与应用》等。特别是毛子青大牛的论文,值得一...

    我知道,我现在写这篇文章还很不成熟,因为我很多东西弄得还很不怎么样,但是我还是想写一下。

    国家集训队论文中有大量关于DP优化的论文:毛子青的《动态规划算法的优化技巧》、朱晨光的《从《鹰蛋》一题浅析对动态规划算法的优化》、杨哲的《凸完全单调性的一个加强与应用》等。特别是毛子青大牛的论文,值得一看!还要说明的是,周源的《浅谈数形结合思想在信息学竞赛中的应用》一文,谈到了数形结合、单调队列、和下凸折线上凸折线等,分析了斜率的优化策略。赵爽的《动态规划加速原理之四边形不等式》给出了四边形不等式的证明。关于斜率优化的证明在网上百度一下应该有很多的。

            关于DP的优化,真是五花八门,种类繁多!具体的有:

    1)线段树(优化转移决策数)

    2)状态压缩(优化空间 和时间)

    3)斜率优化 (优化转移决策数)

    4)四边形优化 (优化转移决策数)

    5)滚动数组 (优化空间)

    6)矩阵优化  ()


    例题:

    线段树:

        hdu 3016 ManDown 

        pku 2374 Fence Obstacle Course

        poj 3378 Crazy Thairs

        这两个都是简单的题目,其他的我没有记录,以后遇到在添加吧

    状态压缩:骨牌覆盖 炮兵阵地  这两个很经典!

            再者状态压缩还有一类很难得!虽然放在这儿有点牵强,叫做基于连通性状态压缩动态规划,俗名叫插头DP。

    斜率优化 :

            首先是单调队列:

            poj 2823

            hdu 3530 Subsequence

            hdu 3415 网上百度一下即可

            然后就是斜率优化的DP

            hdu 3507 Print Article

            poj 3709 K-Anonymous Sequence

            注意:延迟加入这个东东

    四边形优化:

           hdu 3516 Tree Construction

           hdu 1729 An old Stone Game(经典)

            记得还有一个,邮局问题,邮局的那个很经典!!!

    关于凸完全单调性的一个加强与应用

    展开全文
  • [dp优化]个人对dp优化的理解

    千次阅读 2016-02-05 13:34:25
    动态规划优化 矩阵乘法 单调队列 斜率优化 决策单调性 四边形不等式

    引言

    dp 所要解决的是多阶段决策问题,它利用递归的思想,将规模为n的问题转化为规模较小的问题,直到转化为小到能够直接求解的子问题。通常来说这样做时间复杂度是指数级的,但是如果所有不同的子问题的数目是多项式级别,那么多项式时间就可以解决这个问题,这就是 dp 的本质
    dp
    (1)
    (2)
    (3)
    O(nt)O(ne)tD/eD
    这样可以得到四类典型的动态规划方程
    1D/1D:D[0]
    E[j]=min { D[i]+w(i,j) } f(j)i<j
    2D/0D:D[i][0]D[0][j]
    E[i][j]=min { D[i1][j]+xi,D[i][j1]+yi,D[i1][jz]+zi,j }
    2D/1D:D[i][i]=0
    E[i][j]=w(i,j)+min { C[i,k1]+C[k,j] } i<kj
    2D/2D:D[i,0]D[0,j]
    E[i][j]=min { D[i][j]+w(i+j,i+j) } 0i<i,0j<j
    dpO(ne+t)
    dp 优化无外乎状态优化和转移优化两种手段,状态优化往往依赖于具体题目而变,我们主要研究的是转移优化,转移优化常见的手段有:斜率优化,四边形不等式优化和具体数据结构优化等等,还有一类特殊的针对递推线性的优化即矩阵乘法

    一些准备知识

    移动窗口:单调队列简介

    单调队列是应对较为简单的具有单调性的问题的有力手段,而单调队列的使用不外乎下面五个要点
    (1)
    (2)
    (3)ijijjii
    (4) :由前面我们知道,队列里的决策时刻满足后面的决策比前面的决策后出现,且更劣
    (5) 最优选择在队首:如果后面有一个决策比队首更优,那么它将成为队首,由队列的单调性也可知这一点

    动态凸壳:平衡树的应用

    前面提到这里的单调性经常与凸包挂钩,而我们时常要维护的是决策点在决策平面上的一个上凸壳或是下凸壳
    使(x,y)x

    动态凸壳:神器的CDQ分治

    在动态凸壳问题中我们还可以用CDQ分治来解决,这里不多赘述了。

    1D/1D优化 f[i]=min { f[j]+w(i,j) }

    第一种情况:分离决策与状态

    这一类优化针对的是这样一类 w(i,j)
    w(i,j)=μ(i)+ϕ(j)
    也就是说 w(i,j)iμjϕ

    (1) f(j)
    (2) f(j)线

    第二种情况:斜率优化

    这一类优化针对的是这样一类方程
    f(i)=min { aixj+biyj }

    jxj,yj 将每一个决策视作一个点 (xj,yj)
    现在我们的决策平面上有很多点,那么我要寻找的是这样一个点使得
    P=aix+biy
    我们将这个式子变形,有
    y=aibi+Pbi
    这个式子代表的是一个直线,这个直线过决策点 (x,y) ,且斜率为一个定值,而 P 最优就意味着纵轴截距最优,也就是说,现在我过每一个决策点作一条相同斜率的直线,求纵轴截距最优的那个点
    显然这个点只可能存在于所有点的凸壳上(具体是上凸壳还是下凸壳视情况而定),在凸壳上寻找这个点我们只需要二分斜率即可(斜率单调的话直接可以用第一个点或最后一个点),而维护凸壳我们使用平衡树即可(如果横坐标单调就不用这么麻烦了,使用单调队列即可)

    第三种情况:决策单调性优化


    f(i)=min(f(j)+w(i,j))
    w(i,j)
    w(i,j+1)w(i,j)>=w(i+1,j+1)w(i+1,j)
    w
    注:满足这个不等式就意味着w满足四边形不等式,下面会提到

    满足这个不等式等价于
    k(x)xij,k(i)k(j)

    这样,我们可以使用一个栈来维护数据,栈中的每一个元素保存每一个决策是最优的起始位置和终止位置(这显然是一个区间,我们称之为这个决策的作用区间),显然这些区间相互连接且递增
    首先我们要寻找最优决策就是要寻找当前状态在哪个决策的作用区间里,由区间的单调性我们二分即可
    每次我们还要加入一个新决策,我们从后往前扫描栈,扫到一个老决策的时候,我们做这样两件事:
    (1) 如果这个老决策的作用区间的起始位置仍然不如新决策优,那么我们弹出老决策,将老决策的作用区间整个合并到新决策中,继续往前扫
    (2) 如果不满足前面的条件,在老决策的作用区间中二分出新决策起作用的起始位置,将老决策分割,新决策入栈,结束扫描过程

    2D/1D优化:四边形不等式优化 f(i,j)=w(i,j)+min { f(i,k1)+f(k,j) }

    四边形不等式
    i<i<j<jw(i,j)+w(i,j)w(i,j)+w(i,j)w
    区间包含关系的单调性
    i<i<j<jw(i,j)w(i,j)w
    【定理1】
    wf

    我们定义 s(i,j)f(i,j)
    【定理2】
    s(i,j1)s(i,j)s(i+1,j)

    这样转移方程从原来的
    f(i,j)=w(i,j)+min { f(i,k1)+f(k,j) } ikj
    变成了
    f(i,j)=w(i,j)+min { f(i,k1)+f(k,j) } s(i,j1)ks(i+1,j)
    复杂度从 O(n3)O(n2)

    线性递推优化:矩阵乘法

    一般地,对于 m 项递推式,我们记递推式为
    fn+m=m1i=0bifn+i

    我们就可以把递推式写成如下矩阵形式

    an+man+m1an+1

    =

    bm1100bm2010b1001b0000

    ×

    an+m1an+m2an

    然后就可以在 O(m3logn) 时间内解决

    展开全文
  • DP优化:矩阵乘法

    2019-05-04 23:01:20
    咳咳咳,今天讲的是DP的一种优化策略——矩阵乘法 关于能用矩阵乘法优化DP题目,有如下几个要求: 转移式只有加法,清零,减法etc.,max和min运算不允许 转移式中关于前几位dp结果得到的系数必须是常量 转移...
  • 使用II型KDP优化正交频率转换以产生1053 nm的纳秒线性调频脉冲的二次谐波
  • 5.20-DP优化总结

    2017-05-20 20:48:32
    说总结事实上并不算是到了总结的时候,因为ppt上面的题我还没有刷完,尤其是树形DP,现在也没做几道题,但Dp是没有模板的除了斜率优化有差不多的结构,其他DP都千奇百怪。 先说有优化dp,这是最好想出暴力方程的...
  • 关于dp优化的问题

    2015-01-28 14:54:19
    dp已经是一个很优化的算法,能用很短的时间解决问题能将复杂度降到很低。但是dp也存在优化,这样使dp更加有效。  dp优化分:单调队列优化、斜率优化、四边形优化。  我觉的单调队列优化是斜率优化的一种特殊...
  • 单调队列优化DP的原理,经典例题“多重背包”的多种解法
  • 标题说的三个玩意都差得不是很多。 上论文 :WQS二分 例 : 在树上选k条路径使得权值和最大。...既然在DP中加一维不可取,我们只能直接DP。 但是DP出来的结果并不一定是选了k个的。 大佬开始了他的妄想,要是...
  • poj1088 滑雪(dfs、dp优化

    千次阅读 2014-08-12 15:14:13
    #include #include #include #include #include #include #include #include #define N 110 int a,b,step=0; int anw=0;...int dp[N][N]; int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; using
  • 从快速幂到dp 优化:矩阵快速幂

    千次阅读 2017-07-14 21:05:06
    不太熟悉dp 或者经常做蓝桥杯题目的,可能一看这题就开始写搜索的代码了,确实,很多dp 也可以说是搜索的优化,因为搜索的状态太多,于是就将重复的搜索状态记录下来,这样就可以减少大量无用的搜索,这大概就是...
  • 参考资料 本题tyvj题解 ...这个题目很好的呈现了dp优化过程,最后还是可以用单调队列优化到Θ(N),不过Θ(NlgN)已经可以AC了。把dp变为贪心,再用其他手段可以大大优化dp的复杂度。 Ps: ...
  • Noip2015 Day1 T3 斗地主(Dfs+Dp优化

    千次阅读 2017-08-17 17:37:27
    一道需要dp作预处理的题,想通了之后觉得还好,就是代码写的绝望
  • 在空间上,我们可以使用滚动数组进行优化,节省空间。在时间上,我们注意到,对于相同的i,如果对j由大到小枚举,会有重叠的部分,可以直接以O(1)的复杂度得到 min{dp[k][i]},从而把复杂度降到了O(M*N) AC代码...
  • 先上一道例题:Bridging signals POJ - 1631 ...然而,常规的dp复杂度是 O(n^2) ,这道题会愉快地TLE,所以要进行nlogn级别的优化。 //O(n^2) TLE #include&lt;cstdio&gt; #include&lt;algorith...
  • DP优化】 2577 How to Type   1513 Palindrome   1025 Constructing Roads In JGShining's Kingdom 3351 Seinfeld   1978 How many ways   2686 Matrix   3376 Matrix ...
  • 单调队列优化dp

    2019-04-06 10:23:49
    一、1D/1D动态规划 有一些动态规划,有着状态数为O(n),每一个状态决策量为O(n)的动态规划方程。...二、dp优化之单调队列优化 在1D/1D动态规划中,有一种dp,转移方程一般为: dp[i]=min(f[j])+g[i],(...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 97,519
精华内容 39,007
关键字:

dp优化