[SDOI2015][bzoj4518] 征途 [斜率优化dp]

时间:2021-06-11 03:02:44

题面

传送门

思路

把$vm^2$展开化一下式子,可以得到这样的等价公式:

$vm2=m\sum_{i=1}m a_i2-\sum_{i=1}m a_i$

那么我们要最小化的就是$\sum_{i=1}^m a_i^2$这个东西

设$dp[i][j]$表示前i段路程走了j天

转移显然:$dp[i][j]=min(dp[k][j-1]+dis(k,i)^2)(k=1...i-1)$

这就是个模板的斜率优化dp了

总复杂度$O(nm)$

Code:

写代码的时候需要注意一点:当前这一层的状态,要等到这一层(同一个i)都推完了,再一起入队,不然容易互相之间造成影响,导致WA

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
inline int read(){
int re=0,flag=1;char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') flag=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re*flag;
}
int n,m,a[3010],q[3010][3010],l[3010]={0},r[3010]={0},maxq=3000;
ll dp[3010][3010],pre[3010];
ll up(int x,int y,int k){
return dp[x][k]-dp[y][k]+pre[x]*pre[x]-pre[y]*pre[y];
}
ll down(int x,int y,int k){
return 2ll*(pre[x]-pre[y]);
}
int main(){
n=read();m=read();int i,j;
for(i=1;i<=n;i++) a[i]=read(),pre[i]=pre[i-1]+a[i];
q[0][r[0]++]=0;
for(i=1;i<=n;i++){
for(j=max(1,m+i-n)-1;j<i;j++){//先取得状态
while(l[j]<r[j]-1&&up(q[j][l[j]+1],q[j][l[j]],j)<down(q[j][l[j]+1],q[j][l[j]],j)*(ll)pre[i]) q[j][l[j]++]=0;
dp[i][j+1]=dp[q[j][l[j]]][j]+(pre[i]-pre[q[j][l[j]]])*(pre[i]-pre[q[j][l[j]]]);
}
for(j=max(1,m+i-n);j<=i;j++){//分开入队
while(l[j]<r[j]-1&&up(i,q[j][r[j]-1],j)*down(q[j][r[j]-1],q[j][r[j]-2],j)<=down(i,q[j][r[j]-1],j)*up(q[j][r[j]-1],q[j][r[j]-2],j)) q[j][--r[j]]=0;
q[j][r[j]++]=i;
}
}
ll ans=0,mm=m;
ans=mm*dp[n][m]-pre[n]*pre[n];
cout<<ans;
}

[SDOI2015][bzoj4518] 征途 [斜率优化dp]的更多相关文章

  1. P4072 &lbrack;SDOI2016&rsqb;&lpar;BZOJ4518&rpar; 征途 &lbrack;斜率优化DP&rsqb;

    题目描述 Pine开始了从S地到T地的征途. 从S地到T地的路可以划分成n段,相邻两段路的分界点设有休息站. Pine计划用m天到达T地.除第m天外,每一天晚上Pine都必须在休息站过夜.所以,一段路 ...

  2. 洛谷 P4072 &lbrack;SDOI2016&rsqb;征途 斜率优化DP

    洛谷 P4072 [SDOI2016]征途 斜率优化DP 题目描述 \(Pine\) 开始了从 \(S\) 地到 \(T\) 地的征途. 从\(S\)地到\(T\)地的路可以划分成 \(n\) 段,相 ...

  3. bzoj-4518 4518&colon; &lbrack;Sdoi2016&rsqb;征途&lpar;斜率优化dp&rpar;

    题目链接: 4518: [Sdoi2016]征途 Description Pine开始了从S地到T地的征途. 从S地到T地的路可以划分成n段,相邻两段路的分界点设有休息站. Pine计划用m天到达T地 ...

  4. bzoj4518&lbrack;Sdoi2016&rsqb;征途 斜率优化dp

    4518: [Sdoi2016]征途 Time Limit: 10 Sec  Memory Limit: 256 MBSubmit: 1657  Solved: 915[Submit][Status] ...

  5. 【bzoj4518】&lbrack;Sdoi2016&rsqb;征途 斜率优化dp

    原文地址:http://www.cnblogs.com/GXZlegend/p/6812435.html 题目描述 Pine开始了从S地到T地的征途. 从S地到T地的路可以划分成n段,相邻两段路的分界 ...

  6. BZOJ 4518&colon; &lbrack;Sdoi2016&rsqb;征途 &lbrack;斜率优化DP&rsqb;

    4518: [Sdoi2016]征途 题意:\(n\le 3000\)个数分成m组,一组的和为一个数,求最小方差\(*m^2\) DP方程随便写\(f[i][j]=min\{f[k][j-1]+(s[ ...

  7. bzoj4518征途 斜率优化

    征途这是一道十分经典的斜率优化 我们可以从题目中的方差来想,也就很容易的到这个式子 \[ans=m^2*\frac{\sum_{i=1}^{m}{(x_i-{\overline{x}})^2}}{m} ...

  8. &lbrack;SDOI2016&rsqb;征途 —— 斜率优化DP

    时隔多年没有碰斜率优化了... 想当年被斜率优化虐的死去活来,现在看看...也就那样吧. Pine开始了从S地到T地的征途. 从S地到T地的路可以划分成n段,相邻两段路的分界点设有休息站. Pine计 ...

  9. 斜率优化dp 的简单入门

    不想写什么详细的讲解了...而且也觉得自己很难写过某大佬(大米饼),于是建议把他的 blog 先看一遍,然后自己加了几道题目以及解析...顺便建议看看算法竞赛(蓝皮书)的 0x5A 斜率优化(P294 ...

随机推荐

  1. flddler使用方法

    http://blog.csdn.net/geekgjie/article/details/8029936

  2. Volley(二)—— 基本Request对象 &amp&semi; RequestQueue&amp&semi;请求取消

    详细解读Volley(一)—— 基本Request对象 & RequestQueue&请求取消 Volley它非常适合去进行数据量不大,但通信频繁的网络操作,而对于大数据量的网络操作, ...

  3. &quot&semi;未能找到类型或命名空间名称&quot&semi;&comma;引用dll的时候出错

    当前项目是.net2.0框架,引用的dll是 .net 4.5框架,引用后编译时报错“未能找到类型或命名空间名称”. 当前项目 右键-->应用程序-->目标框架 改为 .net frame ...

  4. php文件删除unlink&lpar;&rpar;详解

    请记住从PHP文件创建的教训,我们创建了一个文件,名为testFile.txt . $myFile = "testFile.txt"; $fh = fopen($myFile, ' ...

  5. 计算圆周率 Pi &lpar;π&rpar;值&comma; 精确到小数点后 10000 位 只需要 30 多句代码

    大家都知道π=3.1415926……无穷多位, 历史上很多人都在计算这个数, 一直认为是一个非常复杂的问题.现在有了电脑, 这个问题就简单了.电脑可以利用级数计算出很多高精度的值, 有关级数的问题请参 ...

  6. poj1922

    Ride to School Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 18704   Accepted: 7552 D ...

  7. PHP 做 RSA 签名 生成订单(支付宝例子)

    /组合签名 $a=time(); $b=substr($a, 1); //生成随机订单号 $orderid= $b.mt_rand(10000,99999); //合作身份者id,以2088开头的16 ...

  8. 作为新手,SEO要避免的五大误区

    越来越多人在做网站的时候关注的不是网站的界面,而是网站的seo排名.Seo其实没有我们相信中的那么简单,特别对于新手,在实际操作过程中很容易遇到一些误区,今天我们简单说说新手要避免的五大seo误区. ...

  9. java----SVN

    下载SVN server 安装服务器,注意需要配置端口和本地仓库 https://www.visualsvn.com/server/download/ 下载SVN client https://tor ...

  10. Docker&colon; Harbor一些小知识

    镜像文件上传到私有仓库harbor后,镜像的物理存储位置在哪里? 这些信息记录在docker-compose.yml里,通过观察发现 镜像存储在了宿主机的 volumes: - /data/regis ...