当前位置:首页 > IT教程

动态规划之——四边形不等式优化

时间:2020-06-29 22:31:01来源:金橙教程网 作者:admin8 阅读:86次 [手机版]
 

四边形

模型

https://www.luogu.org/Problemnew/show/P1880

在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。

试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.

得出方程:O(n^3)

dp[i][j]=min(dp[i][k]+dp[k+1][j]+cost[i][j])dp[i][j]=min(dp[i][k]+dp[k+1][j]+cost[i][j])dp[i][j]=min(dp[i][k]+dp[k+1][j]+cost[i][j])

四边形优化:O(n^2)

四边形方程:f[a][c]+f[b][d]&lt;=f[b][c]+f[a][d](a&lt;b&lt;=c&lt;d)f[a][c]+f[b][d]&lt;=f[b][c]+f[a][d](a &lt; b &lt;= c&lt; d)f[a][c]+f[b][d]<=f[b][c]+f[a][d](a<b<=c<d)

在这里插入图片描述

  1. 证明cost满足上式;
  2. cost成立时,dp也会满足上式;
  3. best[i][j]=kbest[i][j]=kbest[i][j]=k,表示dp[i][j]dp[i][j]dp[i][j]的最优决策为[i,k]+[k+1,j][i,k]+[k+1,j][i,k]+[k+1,j]。由1,21,21,2得出best[i][j]best[i][j]best[i][j]单调:
    1. best[i][j1]&lt;=best[i][j]&lt;=best[i+1][j]best[i][j-1]&lt;=best[i][j]&lt;=best[i+1][j]best[i][j−1]<=best[i][j]<=best[i+1][j]。
    2. best[i1][j]&lt;=best[i][j]&lt;=best[i][j+1]best[i-1][j]&lt;=best[i][j]&lt;=best[i][j+1]best[i−1][j]<=best[i][j]<=best[i][j+1]。
  4. 那么做dp[i][j]dp[i][j]dp[i][j]时,只需要从best[i][j1]best[i][j-1]best[i][j−1]枚举到best[i+1][j]best[i+1][j]best[i+1][j]即可。

解题

  1. i=acw[i]+i=bdw[i]=i=adw[i]+i=bcw[i]\sum_{i=a}^cw[i]+\sum_{i=b}^dw[i]=\sum_{i=a}^dw[i]+\sum_{i=b}^cw[i]∑i=ac​w[i]+∑i=bd​w[i]=∑i=ad​w[i]+∑i=bc​w[i],成立;
  2. 对于时间复杂度不够的类似二维dp,推荐O(n3)O(n^3)O(n3)打表验证,改成四边形优化很方便的;(绝对不是懒得证明 hahaha)
  3. 在更新dpdpdp的时候维护bestbestbest数组即可。

当然,取最大值显然是一个一个合并最大了。

环形只需要后面再来n个就行

#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL a[209];
LL dp[209][209];
int best[209][209];
LL ma[209][209];

int main(){
    int n;scanf("%d",&n);
    memset(dp,0x3f,sizeof dp);
    for(int i=1;i<=n;i++){
        scanf("%lld",a+i);
        a[i]+=a[i-1];
    }
    for(int i=n+1;i<=2*n;i++){
        a[i]=a[i-1]+a[i-n]-a[i-n-1];
    }
    n*=2;

    for(int i=1;i<n;i++){
        best[i][i+1]=i;
        ma[i][i+1]=dp[i][i+1]=a[i+1]-a[i-1];
    }
    for(int i=1;i<=n;i++){
        dp[i][i]=0;
    }
    LL ans1=1e18,ans2=0;
    for(int len=3;len<=n/2;len++){
        for(int i=1;i+len-1<=n;i++){
            int j=i+len-1;
            ma[i][j]=max(ma[i][j-1],ma[i+1][j])+a[j]-a[i-1];
            for(int k=best[i][j-1];k<=best[i+1][j];k++){
                LL tmp=dp[i][k]+dp[k+1][j]+a[j]-a[i-1];
                if(tmp<dp[i][j]){
                    dp[i][j]=tmp;
                    best[i][j]=k;
                }
            }
            if(len==n/2)ans1=min(ans1,dp[i][j]),ans2=max(ans2,ma[i][j]);
        }
    }
    printf("%lld\n%lld\n",ans1,ans2);
}

相关阅读

优化网页速度的7种方法

周末连续两天给大家讲了面向对象编程的主要特性「封装」和「继承」,如果你期待今天继续讲「多态」这个特性,可能你要失望了,今天并没

XP系统优化秘籍—快速关机与还原

一、关机加速一键待机  打开“控制面板”→“电源选项”,选择“高级”选项卡,在这里设置“在按下计算机电源按钮时”下拉选单,在其

SEO优化中查询检索词与加#搜索的操作方法

最近看见一篇在讲查询词,检索词的文章,平头哥SEO也有这样的亲身实践经历。其实查询词与检索词在我们互联网日常生活中,经常被使用到

淘宝如何优化宝贝属性?详细的步骤介绍

在淘宝开店的朋友们应该都知道做好淘宝优化工作的重要性,做好优化可以提高淘宝点击率、转化率,从而提高店铺销量。今天金橙教程网小

sql优化之使用索引

文章转自 https://www.cnblogs.com/AK2012/archive/2013/01/04/2013-0104.html,好文要顶,感谢分享!!!SQL索引在数据库优化中占有一个非

分享到:

IT相关

程序相关

推荐文章

热门文章