【Educational Codeforces Round 11-F. Bear and Bowling 4】斜率优化DP+二分_综合

Bear and Bowling 4

题目链接：

https://codeforces.com/contest/660/problem/F

Description

在这里插入图片描述

Input

在这里插入图片描述

Output

在这里插入图片描述

Sample Input

6
5 -1000 1 -3 7 -8

Sample Output

Hint

在这里插入图片描述

题意

定义一个长度为n的数组a的权值为 $∑i=1ni?a[i]\sum_{i=1}^{n} i*a[i]$ ,给出一个数组，找出一个连续子序列,让这个子序列的权值最大。

题解

首先想一下n^2的DP方程。

我们设 $dp[i]=∑j=1ij?a[j]，sum[i]=∑j=1ia[j]dp[i]=\sum_{j=1}^{i} j*a[j]，sum[i]=\sum_{j=1}^{i} a[j]$

那么以i为结尾的最大权值的连续子序列的权值为ans[i]

$max\{dp[i]-dp[j]-j*(sum[i]-sum[j])\} ...(0\leq j < i)$

看这个方程大概就可以斜率DP。

我们进行推导一下，设 $k < j < i$ ,当 $j$ 比 $k$ 更优的时候：

? $d p [i] ? d p [j] ? j ? (s u m [i] ? s u m [j]) > d p [i] ? d p [k] ? k ? (s u m [i] ? s u m [k])$

$= > d p [j] + j ? s u m [i] ? j ? s u m [j] < d p [k] + k ? s u m [i] ? k ? s u m [k]$

$= > s u m [i] ? (j ? k) < d p [k] ? k ? s u m [k] ? (d p [j] ? j ? s u m [j])$

$= > s u m [i] ? (j ? k) < j ? s u m [j] ? d p [j] ? (k ? s u m [k] ? d p [k])$

$\frac{j*sum[j]-dp[j]-(k*sum[k]-dp[k])}{(j-k)}$

我们发现如果设 $f [x] = x ? s u m [x] ? d p [x]$ 那么 $s u m [i]$ 就是 $g (j, k)$ 的斜率。

还是设 $k < j < i$ ，如果存在 $g [i, j] > g [j, k]$ ，那么j这个点就一定是没用的，这里我们来证明一下。

1.当 $g [i, j] > s u m [i]$ ,说明 $i$ 比 $j$ 更优,此时j是没用的。

2.当 $g[i,j]≤sum[i]g[i,j]\leq sum[i]$ ,但是又存在 $\leq sum[i]$ ，由于 $g [j, k] < s u m [i]$ 说明此时k是比j更优的,此时j也是没用的。

所以我们可以通过上面的优化去除掉所有 $g [i, j] > g [j, k]$ 的情况，所以从左到右斜率呈现一个递减的情况，也就是一个上凸包。

但是由于本题中sum[i]不是递增的，所以不能通过弹出队首的方法优化斜率DP，我们只能在维护好的凸包上二分找到最优解。

二分的时候设 $F (m i d)$ 为mid能得到的最大值,如果 $F (m i d) > = F (m i d + 1)$ 说明最优解在左侧，否则在右侧。

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<time.h>
#include<math.h>
using namespace std;//***********************IO**********************************
namespace fastIO
{
    #define BUF_SIZE 100000#define OUT_SIZE 100000bool IOerror=0;inline char nc(){
    static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;if (p1==pend){
    p1=buf;pend=buf+fread(buf,1,BUF_SIZE,stdin);if (pend==p1){
    IOerror=1;return -1;}}return *p1++;}inline bool blank(char ch){
    return ch==' '|ch=='\n'||ch=='\r'||ch=='\t';}inline void read(int &x){
    bool sign=0;char ch=nc();x=0;for (; blank(ch); ch=nc());if (IOerror)return;if (ch=='-')sign=1,ch=nc();for (; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';if (sign)x=-x;}#undef OUT_SIZE#undef BUF_SIZE
};
using namespace fastIO;
//************************************************************************#define ok cout<<"OK"<<endl;
#define dbg(x) cout<<#x<<" = "<<x<<endl;
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl;
#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endl;
#define print(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
#define pb push_back
#define Fi first
#define Se second
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>const double eps = 1e-8;
const double PI = acos(-1.0);
const int Mod = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 2e5+10;
ll dp[maxn],sum[maxn],a[maxn],res[maxn];
int q[maxn],top;
ll GET(int i,int j)
{
    return dp[i]-dp[j]-1LL*j*(sum[i]-sum[j]);
}
ll Y(int x)
{
    return 1LL*x*sum[x]-dp[x];
}
int main()
{
    int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i],dp[i]=dp[i-1]+1LL*i*a[i];q[++top]=0;for(int i=1;i<=n;i++){
    int l=1,r=top-1;while(l<=r){
    int mid=(l+r)>>1;if(GET(i,q[mid])>=GET(i,q[mid+1])) r=mid-1;else l=mid+1;}res[i]=max(a[i],GET(i,q[l]));while(top&&(Y(i)-Y(q[top]))*(q[top]-q[top-1])>(Y(q[top])-Y(q[top-1]))*(i-q[top])) top--;q[++top]=i;}ll ans=0;for(int i=1;i<=n;i++) ans=max(ans,res[i]);printf("%lld\n",ans);return 0;
}