0x5A~0x5B

作者:无名 - 其它综合 -

目录

  • 0x5a~0x5b
    • 0x5a 斜率优化
    • 0x5b 四边形不等式

0x5a~0x5b

0x5a 斜率优化

之前已经写过一些不再写一遍了。

here

0x5b 四边形不等式

a.[√]诗人小g

题目传送

sol:

首先直接设出状态:\(f[i]\)表示前i首诗排版后的最小答案。

那么转移为:
\[ f[i]=min_{0≤jlt;i}\{f[j]+|sum[i]-sum[j]+i-j-1-l|^p\} \]
由于存在高次,不符合单调队列优化和斜率优化,考虑四边形不等式优化。

令\(val(j,i)=|sum[i]-sum[j]+i-j-1-l|^p\),

因为存在\(jlt;i\),那么只需证明\(val(j,i+1)+val(j+1,i)≥val(j,i)+val(j+1,i+1)\),

也即证明\(val(j+1,i)-val(j+1,i+1)≥val(j,i)-val(j,i+1)\)。

令\(a=(sum[i]+i)-(sum[j]+j)-(l+1),b=(sum[i]+i)-(sum[j+!]+j+1)-(l+1)\)

则只需证明:\(|a|^p-|a+(s[i+1]+1)|^p≥|b|^p-|b+(s[i+1]+1)|^p\)

由于\(alt;b\),所以等价于只要证明函数\(y=|x|^p-|x+c|^p\ (c为常数)\)单调递减,分类讨论求导可证。

所以就可以套决策单调性的板子了。

code:

#includelt;cmathgt;
#includelt;stringgt;
#includelt;cstdiogt;
#includelt;cstringgt;
#includelt;algorithmgt;
#define rg register
#define il inline
#define ll long long
#define db long double
using namespace std;

il int gi() {
   rg int x=0,w=0; char ch=getchar();
   while (chlt;#39;0#39;||chgt;#39;9#39;) {if (ch==#39;-#39;) w=1;ch=getchar();}
   while (chgt;=#39;0#39;amp;amp;chlt;=#39;9#39;) x=x*10+(ch^48),ch=getchar();
   return w-x:x;
}

const int n=1e5+3;

char ch[n][33];
int n,h,t,l,p,a[n],s[n];
db f[n];

struct rec{int x,l,r;}q[n];

il db qpow(int x,int p) {
    rg db a=x,ans=1.0;
    for(;p;pgt;gt;=1,a=a*a)
        if(pamp;1) ans=ans*a;
    return ans;
}

il db calc(int i,int j) {return f[j]+qpow(abs(s[i]-s[j]+i-j-1-l),p);}

il int search(int i) {
    rg int l=q[t].l,r=q[t].r,mid;
    while(llt;r) {
        mid=l+rgt;gt;1;
        if(calc(mid,i)lt;=calc(mid,q[t].x)) r=mid;
        else l=mid+1;
    }
    return r;
}

il void print(int i) {
    if(!i) return;
    print(a[i]);
    for(rg int j=a[i]+1;jlt;=i;++j) {
        printf(%s,ch[j]);
        if(j!=i) putchar(#39; #39;);
    }
    putchar(#39;\n#39;);
}

int main()
{
    rg int i,t=gi();
    while(t--) {
        n=gi(),l=gi(),p=gi();
        for(i=1;ilt;=n;++i)
            scanf(%s,ch[i]),s[i]=s[i-1]+strlen(ch[i]);
        h=1,t=0,q[++t]=(rec){0,1,n};
        for(i=1;ilt;=n;++i) {
            if(hlt;=t) {
                if(q[h].r==i-1) ++h;
                else q[h].l=i;
            }
            f[i]=calc(i,q[h].x),a[i]=q[h].x;
            rg int pos=n+1;
            while(hlt;=t) {
                if(calc(q[t].l,i)lt;=calc(q[t].l,q[t].x)) pos=q[t--].l;
                else {
                    if(calc(q[t].r,i)lt;=calc(q[t].r,q[t].x)) 
                        pos=search(i),q[t].r=pos-1;
                    break;
                }
            }
            if(poslt;=n) q[++t]=(rec){i,pos,n};
            // 决策i是pos~n的最优决策
        }
        if(f[n]gt;1e18) puts(too hard to arrange);
        else printf(%lld\n,(ll)f[n]),print(n);
        puts(--------------------);
    }
    return 0;
}

b.[√] 合并石子

题目传送

sol:

\(o(n^3)\)的很熟悉了,直接写:
\[ f[i,j]=\min_{i≤klt;j}{}\{f[i,k]+f[k+1,j]\}+\sum_{k=i}^ja[k] \]
打表发现其具有决策单调性(不会证明),则可以使复杂度降为\(o(n^2)\)。

值得一提的是:

3方dp中i是倒序枚举的,j是正序枚举的,则利用到的是:

\(p[i,j-1]≤p[i,j]≤p[i+1,j]\ (p[x,y]代表状态(x,y)的最优决策)\)

而对于其他可以用决策单调性优化的转移,若原始转移中i是正序枚举,j是倒序枚举,则有:

\(p[i-1,j]≤p[i,j]≤p[i,j+1]\ (p[x,y]代表状态(x,y)的最优决策)\)

应该只要符合决策单调性,就能套上这两种情况中的一种。

另外luogu上的这题还有最大值要求,但最大值不满足决策单调性,但是它却必然是如下转移得到最优:

\(g[i,j]=max\{g[i,j-1],a[i+1,j]\}+\sum_{k=i}^ja[k]\) 原理应是贪心。

code:

#includelt;cmathgt;
#includelt;stringgt;
#includelt;cstdiogt;
#includelt;cstringgt;
#includelt;algorithmgt;
#define rg register
#define il inline
#define ll long long
#define db double
using namespace std;

il int gi() {
   rg int x=0,w=0; char ch=getchar();
   while (chlt;#39;0#39;||chgt;#39;9#39;) {if (ch==#39;-#39;) w=1;ch=getchar();}
   while (chgt;=#39;0#39;amp;amp;chlt;=#39;9#39;) x=x*10+(ch^48),ch=getchar();
   return w-x:x;
}

const int n=903;

int n,ans1,ans2,a[n],s[n],f[n][n],g[n][n],pf[n][n],pg[n][n];

int main()
{
    rg int i,j,k;
    memset(f,0x3f,sizeof(f));
    memset(g,0xcf,sizeof(g));
    for(i=1,n=gi();ilt;=n;++i) a[i]=a[i+n]=gi();
    for(i=1;ilt;=nlt;lt;1;++i)
        f[i][i]=g[i][i]=0,pf[i][i]=pg[i][i]=i,s[i]=s[i-1]+a[i];
    for(i=nlt;lt;1;igt;=1;--i)
        for(j=i+1;jlt;=nlt;lt;1amp;amp;j-i+1lt;=n;++j) {
            for(k=pf[i][j-1];klt;=pf[i+1][j];++k) 
                if(f[i][k]+f[k+1][j]+s[j]-s[i-1]lt;f[i][j])
                    f[i][j]=f[i][k]+f[k+1][j]+s[j]-s[i-1],pf[i][j]=k;
            g[i][j]=max(g[i][j-1],g[i+1][j])+s[j]-s[i-1];
            //最大值没有决策单调性,但是为什么可以是上面那样?  
        }
    ans1=0x3f3f3f3f,ans2=0;
    for(i=1;ilt;=n;++i)
        ans1=min(ans1,f[i][i+n-1]),ans2=max(ans2,g[i][i+n-1]);
    printf(%d\n%d\n,ans1,ans2);
    return 0;
}

c.[√] 邮局

题目传送

sol:

此题不难想到设\(f[i,j]\)表示前面j个村庄建了i个邮局的最小距离和。

转移为:
\[ f[i,j]=min_{0≤klt;j}\{f[i-1,k]+cost(k+1,j)\} \]
关于cost的计算显然取中间值最优。

还是打表发现,f具有决策单调性。

那么注意到此处i正序枚举,j可正可倒,但为了套上面讲到的模型,让j倒序枚举,然后就有:

\(p[i-1,j]≤p[i,j]≤p[i,j+1]\ (p[x,y]代表状态(x,y)的最优决策)\)

但是由于每次枚举到下一个i时,\(p[i,\_]\)全为0,所以需要先把\(p[i,m+1]=m\),然后再转移。

#includelt;cmathgt;
#includelt;stringgt;
#includelt;cstdiogt;
#includelt;cstringgt;
#includelt;algorithmgt;
#define rg register
#define il inline
#define ll long long
#define db double
using namespace std;

il int gi() {
   rg int x=0,w=0; char ch=getchar();
   while (chlt;#39;0#39;||chgt;#39;9#39;) {if (ch==#39;-#39;) w=1;ch=getchar();}
   while (chgt;=#39;0#39;amp;amp;chlt;=#39;9#39;) x=x*10+(ch^48),ch=getchar();
   return w-x:x;
}

const int n=303;
const int m=3003;

int n,m,a[m],f[n][m],p[n][m],pre[m][m],suf[m][m];

il int dist(int l,int r,int mid) {return pre[mid][r]+suf[mid][l];}

il int calc(int l,int r) {
    if((r-l+1)amp;1) return dist(l,r,l+rgt;gt;1);
    else return min(dist(l,r,l+r-1gt;gt;1),dist(l,r,l+r+1gt;gt;1));
}

int main()
{
    rg int i,j,k,tmp;
    m=gi(),n=gi();
    for(i=1;ilt;=m;++i) a[i]=gi();
    sort(a+1,a+m+1);
    for(i=1;ilt;=m;++i)
        for(j=i+1;jlt;=m;++j)
            pre[i][j]=pre[i][j-1]+a[j]-a[i];
    for(i=m;igt;=1;--i)
        for(j=i-1;jgt;=1;--j)
            suf[i][j]=suf[i][j+1]+a[i]-a[j];
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(i=1;ilt;=n;++i) {
        p[i][m+1]=m;
        for(j=m;jgt;=1;--j)
            for(k=p[i-1][j];klt;=p[i][j+1];++k) {
                tmp=f[i-1][k]+calc(k+1,j);
                if(tmplt;f[i][j]) f[i][j]=tmp,p[i][j]=k;
            }
    }
    printf(%d\n,f[n][m]);
    return 0;
}

0x5a~0x5b

原文地址:https://www.cnblogs.com/bhllx/p/11006323.html

IT人知识库 原文地址:http://www.itpeo.net/9999/4539858.html





标签

[poj]3281Dining

原题 题目大意 n头奶牛,只能吃某种食物和饮料(而且只能吃特定的一份) 一种食物被一头牛吃了之后,其余牛就不能吃了 第一 ...

西南seo大神理解的互联网+

“农村将成为互联网领域的‘沃土’,而非信息时代失联的‘孤岛’。大力发展农村互联网,打造现代智慧农村。在农村产业结构调整、 ...

新媒体的冲击,传统企业的出路在哪?

新媒体冲击,传统企业的出路在哪? 在二零壹伍克强总理提出我们进入互联网+时代起,我国正式宣布进入后互联网时代,在互联网新 ...

「mysql优化专题」详解引擎(InnoDB,MyISAM)的内存优化攻略?(9)

注意:以下都是在mysql目录下的my.ini文件中改写(技术文)。 一、innodb内存优化 innodb用一块内存区 ...

Django==>Form组件

django ==gt; form 组件 目录: 1.基本使用 2.form中字段和插件 3.自定义验证规则 4.动态加 ...

AndroidStudio解决ADB检测不到手机导致无法连接的问题

adb的全称是android debug bridge,是用来管理模拟器和真机的通用调试工具。   开usb调试 ...

iOS的match函数

1.求余 extern double fmod(double,double); fmod(10.2,3) =1.2 ...

.Net基础之3——运算符

(3)convert类型转换 1、类型如果相兼容的两个变量,可以使用自动类型转换或者显示类型转换。 但是如果两个类型的变 ...

c++string去除首尾空格、\n、\r、\t

string s = " test "; size_t n = s.find_last_not ...

安装使用Hadoop遇到的一些问题

安装完后却不能运行hadoop,仔细查看日志信息,hadoop记录了详尽的日志信息,日志文件保存在logs文件夹内。 ...

安全的企业邮箱如何选择

目前市场上能说得上品牌的企业邮箱超过30个,如果计算上没有品牌的,或者是主营业务是网站建设也在做企业邮箱的,可以用多如牛 ...

springboot学习总结(三)RestTemplate用法

(一)配置类 package com.vincent.demo.config; import org.springf ...

C#Emgu类型转换

bitmap:   bitmap位图文件,是windows标准格式,也是.net主要的图像存储格式。   bitmap ...

BS4库详解

1 from bs4 import beautifulsoup 2 3 4 5 6 ...

微信小程序(五)

javascript:   javascript 是一种轻量的,解释型的,面对对象的头等函数语言,是一种动态的基于原型和 ...

linux安装维护

samba installation and setup 1. install sudo apt-get instal ...

【UOJ274】【清华集训2016】温暖会指引我们前行LCT

【uoj274】【清华集训2016】温暖会指引我们前行 任务描述 虽然小r住的宿舍楼早已来了暖气,但是由于某些原因,宿舍 ...

string和newstring()的区别,以及equals与==的去别

import java.util.scanner; public class testscanner { pu ...

自己喜欢的一些句子摘录--2017-09-09

自己喜欢的一些文章中的句子摘录、、、 ================= 生活中最重要的就是选择,太多的选择让我们不知所 ...

java核心编程——IO流之字符流和字节流相互转换(四)

1.为什么字符流和字节流需要转换?   这是因为有一些时候系统给你提供的只有字节流,比如说system.in标准输入流。 ...