首页 / 算法 / 算法复习——1D/1Ddp优化

算法复习——1D/1Ddp优化

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法复习——1D/1Ddp优化，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2183字，纯文字阅读大概需要4分钟。

内容图文

搬讲义~~~~

技术分享 技术分享 技术分享 技术分享 技术分享 技术分享

题目1：玩具装箱(bzoj1010)

Description

P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为1…N的N件玩具，第i件玩具经过压缩后变成一维长度为Ci.为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地说如果将第i件玩具到第j个玩具放到一个容器中，那么容器的长度将为 x=j-i+Sigma(Ck) i<=K<=j 制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为x,其制作费用为(X-L)^2.其中L是一个常量。P教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过L。但他希望费用最小.

Input

第一行输入两个整数N，L.接下来N行输入Ci.1<=N<=50000,1<=L,Ci<=10^7

Output

输出最小费用

Sample Input

5 4
3
4
2
1
4

Sample Output

1
 
经典的决策单调性问题··但也可以用斜率优化····维护一个栈，栈中维护每个决策以及用到它的最优状态的左右区间··每次先更新状态然后将其作为决策二分查找替换栈中决策即可···
另外由于决策单调性是建立在平行四边形不等式的基础上的··而那个东西证起来很麻烦····做题的时候也不容易反应过来··所以尽量还是打表来寻找决策单调性··
 
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstring>
#include<string>
#include<algorithm>
usingnamespace std;
constint N=5e4+5;
longlong sum[N],f[N];
struct node
{
  int l,r,pos;
}que[N];
int n,L,head,tail;
inline int R()
{
  char c;int f=0;
  for(c=getchar();c<‘0‘||c>‘9‘;c=getchar());
  for(;c<=‘9‘&&c>=‘0‘;c=getchar())  f=(f<<3)+(f<<1)+c-‘0‘;
  return f;
}
inline longlongget(int j,int i)
{
  return f[j]+(longlong)(sum[i]-sum[j]+i-j-1-L)*(sum[i]-sum[j]+i-j-1-L);
}
inline int find(node a,int b)
{
  int le=a.l,ri=a.r;
  while(le<=ri)
  {
    int mid=(le+ri)/2;
    if(get(b,mid)<get(a.pos,mid)) ri=mid-1;  
    else le=mid+1;
  }
  return le;
}
inline void work()
{
  head=1,tail=0;
  node temp;temp.l=0,temp.r=n,temp.pos=0;que[++tail]=temp;
  for(int i=1;i<=n;i++)
  {
    while(que[head].r<i)  head++; 
    f[i]=get(que[head].pos,i);
    if(head>tail||get(i,n)<get(que[tail].pos,n))
    {
      while(head<=tail&&(get(i,que[tail].l)<get(que[tail].pos,que[tail].l))) tail--;
      if(head<=tail)
      {
        int t=find(que[tail],i);
        que[tail].r=t-1;
        node temp;temp.l=t;temp.r=n;temp.pos=i;
        que[++tail]=temp;
      }
      else 
      {
        node temp;temp.l=i,temp.r=n,temp.pos=i;
        que[++tail]=temp; 
      }
    }
  }
}
int main()
{
  //freopen("a.in","r",stdin);
  n=R();L=R();  
  for(int i=1;i<=n;i++)  sum[i]=R(),sum[i]+=sum[i-1];
  work();cout<<f[n]<<endl;
  return0;
}

 

 

 

原文：http://www.cnblogs.com/AseanA/p/7654500.html

内容总结

以上是互联网集市为您收集整理的算法复习——1D/1Ddp优化全部内容，希望文章能够帮你解决算法复习——1D/1Ddp优化所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1311120.html

来源：【匿名】