关键词：
这是第一次写斜率优化DP= =。具体的做法参照周源论文《浅谈数形结合思想在信息学竞赛中的应用》。这里仅提供一下AC的代码。
有两点值得注意：1.我这个队列的front和back都是闭区间的；2.在while(...) front++; 这个循环里面，<=写成<就会WA，不知道是为何（讲道理是肯定没问题的，至多多判断几个点而已，我猜想可能是存在了精度误差导致的）。。
代码如下：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <math.h> 5 using namespace std; 6 const int N = 1e5 + 100; 7 8 int n,m; 9 int pre[N]; 10 char s[N]; 11 int que[N]; 12 double cal(int x,int y) 13 { 14 return 1.0 * (pre[y] - pre[x]) / (y - x); 15 } 16 17 int main() 18 { 19 int T; 20 scanf("%d",&T); 21 while(T--) 22 { 23 scanf("%d%d",&n,&m); 24 scanf("%s",s+1); 25 for(int i=1;i<=n;i++) pre[i] = pre[i-1] + s[i] - ‘0‘; 26 int front = 0, back = -1; 27 int ansl = 0, ansr = m; 28 double ans = cal(0, m); 29 int len = m; 30 for(int i=m;i<=n;i++) 31 { 32 int a = i - m; 33 while(front < back && cal(que[back], a) <= cal(que[back-1], a)) back--; 34 que[++back] = a; 35 while(front < back && cal(que[front], i) <= cal(que[front+1], i)) front++; 36 double temp = cal(que[front], i); 37 if(temp > ans) 38 { 39 ans = temp; 40 ansl = que[front]; 41 ansr = i; 42 len = i - que[front]; 43 } 44 else if(fabs(temp-ans) < 1e-8 && len > i - que[front]) 45 { 46 len = i - que[front]; 47 ansl = que[front]; 48 ansr = i; 49 } 50 } 51 printf("%d %d ",ansl + 1, ansr); 52 } 53 return 0; 54 }
uva1451average(斜率优化)
题意：给定一个01序列，让你找出一个长度大于等于F的连续子序列使得平均值最大。析：直接枚举肯定是O(n^3)，超时，然后用前缀和来优化，O(n^2)，还是太大，这个要求的平均值是i>j(sum[i]-sum[j-1])/(i-(j-1))，这正好就是一个斜率... 查看详情
uva1451average(数形结合,斜率优化)
链接：http://vjudge.net/problem/UVA-1451 分析：http://wenku.baidu.com/link?url=ntSYLfzAWxjlfpOKGTac0XYWhtwiMKvn2k1fI__R6JsJVXR_7b9GNijgkX2dPYJqIT5ri7_HS0EmFJZBwxe4bIX8IMWNOcjsMBziIMgC1s3 斜率优化。ave(i,j) 查看详情
1451-average高速求平均值
怎样高速求取一段区间的平均值用前缀的思想来看很easy可是本题题意要求的是大于等于一段长度的区间的平均值的最大值并且给出的数据范围非常大O(n*L)的直白比較算法用于解决此问题不合适这样的情况下能够考虑用斜率来表... 查看详情
斜率优化规律
斜率单调暴力移指针斜率不单调二分找答案x坐标单调开单调队列x坐标不单调开平衡树|cdq分治——摘自MashiroSky ——ta讲解的斜率优化 查看详情
uvalive3902（树上的最优化贪心）
题目链接：https://vjudge.net/problem/UVALive-39021#include<cstdio>2#include<cstring>3#include<vector>4#include<algorithm>5usingnamespacestd;67constintmaxn=1010;8vector<int>gr[ 查看详情
dp斜率优化
斜率优化入门题：PKU3709很多人貌似都是做这道题来K斜率优化的，所以看了资料以后还是开始入手吧。然而还是得跪求大神的程序啊ORZORZ…… 其实理解斜率优化就是会列斜率不等式，还要理解剔除过程。那么我们来看... 查看详情
斜率优化小结
斜率优化小结博主是个智障，总是忘记斜率优化的过程。为了方便以后考前临时抱佛脚，写个博客。斜率优化维护下面的问题：(f_i=min_j<if_j+(a_i-b_j)^2)其中(min)或(max)，和(+)或(-)。(a_i,b_j)均只取决于(i,j)。首先不看取(min)。我们钦... 查看详情
斜率优化dp
斜率优化DP是一种DP的一种优化方式，目的在于将一类具有单调性的DP优化为线性。注：本文只适用于较为基础的斜率优化DP，以便为初学者提供一个思路。这一类可以利用单调性线性或(log)复杂度之内求解的DP问题统称为1D/1D类型... 查看详情
浅谈斜率优化
斜率优化如果对于方程形如这样的我们不能对其进行比较有效果的优化，因为它的转移，涉及到了关于i和关于j的一些数组，这时我们就需要用斜率优化了。通常我们令k<j<i，且用j来更新F[i]比用j优。则有并且我们都可以化... 查看详情
斜率优化
斜率优化说明(本文中所有的单调递增递减都不是绝对的，根据实际情况灵活使用)对于形如\(f[i]=max\)\(f[j]+a[i]+b[i]*c[j]\)的状态转移方程，若\(b[i]\)是单调递增的(可以是递减，但维护方式就不同了，下面不再说明)，那么我们可以对... 查看详情
斜率凸优化小结
斜率凸优化小结前言很久以前考了一道叫做"林克卡特树"的题目(还记得被八省联考支配的恐惧吗？)正解是用直线去切一个凸函数......当时并不是很会。然而\(APIO\)讲课竟然讲了并且卧槽我竟然还听懂了。所以就回来把这... 查看详情
uvalive-8138numbergenerator概率dp+优化(代码片段)
题目链接：https://cn.vjudge.net/problem/UVALive-8138题意有一个随机数生成器，输出1～n的整数。现在已经输出了k个数，问再取几个数才能使取出的所有数的个数至少为2。注意T<=1e5,sumk<=1e5思路（听说存在公式？理论上说有了转移方... 查看详情
斜率优化复习小结
这篇基本上还是自己看的，写一些碎片和注意事项 斜率优化：①形如DP[i]=min/max{DP[j]+A[j]+B[j]*C[i]+D[i]+E}方程，将转移方程化为(DP[j]+A[j])=(-C[i])*(B[j])+(DP[i]-D[i]-E) 即方程斜率式:y=kx+b,其中k=-C[i] 要求C[i]单调！(斜率单调) ... 查看详情
uvalive3708graveyard(最优化问题)
题目描述： 在周长10000的圆上,初始等距的放置着n个雕塑,现在新加入m个雕塑,要使得这n+m个雕塑仍然等距,问原来n个雕塑要移动的距离总和的最小值.原题地址：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=15133分析：... 查看详情
斜率优化dp
hihocoder1529不上升序列[斜率优化]Description给出一个序列(a[1...n])，求构造一个(b[1...n])，满足(b_i+1leb_i)，使得(sumlimits_i=1^n|a_i-b_i|)最小.(nle5 imes10^5)Solution关于暴力与转移方程首先对于暴力转移，定义(dp_i,j)为转移到i点，权 查看详情
斜率优化动态规划学习笔记
发掘状态转移方程的性质发掘状态转移方程的性质本文作者：ztxcsl，使用署名-非商业性使用4.0国际进行许可 查看详情
斜率优化dp
前置知识 比记号与拓展比记号: http://www.cnblogs.com/Sdchr/p/7347799.html [HDU3507]PrintArticle 以[HDU3507]来说明清楚斜率优化. 序列$s_1,s_2,...,s_n$满足$s_1les_2le...les_n$. $f_0=0$. $f_i=min_{0le 查看详情
斜率优化dp和四边形不等式优化dp整理
...一重循环跑i的所有子状态）这样的时间复杂度是O(N^2)而斜率优化或者四边形不等式优化后的DP可以将时间复杂度缩减到O(N)O(N^2)可以优化到O(N),O(N^3)可以优化到O(N^2),依次类推斜率优化DP和四边形不等式优化DP主要的原理就是利用斜... 查看详情