【BZOJ1911】【APIO2010】特别行动队

题面

Description

你有一支由 n 名预备役士兵组成的部队，士兵从 1 到 n 编号，要将他们拆分成若干特别行动队调入战场。出于默契的考虑，同一支特别行动队中队员的编号应该连续，即为形如(i, i + 1, …, i + k)的序列。

编号为 i 的士兵的初始战斗力为 xi ，一支特别行动队的初始战斗力 x 为队内士兵初始战斗力之和，即 X = Xi + Xi+1 + … + Xi+k。通过长期的观察，你总结出一支特别行动队的初始战斗力 x 将按如下经验公式修正为 x'： x' = ax^2 + bx + c，其中 a, b, c 是已知的系数（ a < 0）。

作为部队统帅，现在你要为这支部队进行编队，使得所有特别行动队修正后战斗力之和最大。试求出这个最大和。

例如，你有 4 名士兵， x1 = 2, x2 = 2, x3 = 3, x4 = 4。经验公式中的参数为 a = –1,b = 10, c = –20。此时，最佳方案是将士兵组成 3 个特别行动队：第一队包含士兵1 和士兵 2，第二队包含士兵 3，第三队包含士兵 4。特别行动队的初始战斗力分别为 4, 3, 4，修正后的战斗力分别为 4, 1, 4。修正后的战斗力和为 9，没有其它方案能使修正后的战斗力和更大。

Input

输入由三行组成。第一行包含一个整数 n，表示士兵的总数。第二行包含三个整数 a, b, c，经验公式中各项的系数。第三行包含 n 个用空格分隔的整数 x1,x2, …, xn，分别表示编号为 1, 2, …, n 的士兵的初始战斗力。

Output

输出一个整数，表示所有特别行动队修正后战斗力之和的最大值。

Sample Input

-1 10 -20

2 2 3 4

Sample Output

Hint

20%的数据中， n ≤ 1000；

50%的数据中， n ≤ 10,000；

100%的数据中， 1 ≤ n ≤ 1,000,000， –5 ≤ a ≤ –1， |b| ≤ 10,000,000， |c| ≤10,000,000， 1 ≤ xi ≤ 100。

题解

又是一道斜率优化的DP题目

首先还是写出一个\(O(n^{2})\)的DP

for(int i=1;i<=n;++i)        for(int j=0;j

其中\(F(x)\)是题目中的二次函数\(c[i]\)是前缀和

还是和之前是一样的

假设\(j\)的转移优于\(k\)

那么就有

\[f[j]+F(c[i]-c[j])>f[k]+F(c[i]-c[k])\]

又有

\[F(x)=Ax^{2}+Bx+C\]

直接带入得到

\[f[j]+A(c[i]-c[j])^{2}+B(c[i]-c[j])+C\]

右边同理

然后两边同时减掉一部分得

\[f[j]+Ac[j]^{2}-2Ac[i]c[j]-Bc[j]>f[k]+Ac[k]^{2}-2Ac[i]c[k]-Bc[k]\]

移项得到

\[2Ac[i](c[j]-c[k])<(f[j]+Ac[j]^{2}-Bc[j])-(f[k]+Ac[k]^{2}-Bc[k])\]

除过去搞一下

\[c[i]>\frac{(f[j]+Ac[j]^{2}-Bc[j])-(f[k]+Ac[k]^{2}-Bc[k])}{2A(c[j]-c[k])}\]

然后就可以直接搞了

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             using namespace std;#define ll long long#define MAX 1010000inline int read(){ int x=0,t=1;char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=-1,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*t;}ll A,B,C;ll n,c[MAX];ll F(ll x){return 1LL*A*x*x+1LL*B*x+C;}ll f[MAX];ll s[MAX],h,t;ll sqr(ll x){return x*x;}double count(ll j,ll k){ return ((f[j]-B*c[j]+A*sqr(c[j]))-(f[k]-B*c[k]+A*sqr(c[k])))/(2.0*A*(c[j]-c[k]));}int main(){ n=read();A=read();B=read();C=read(); for(int i=1;i<=n;++i)c[i]=c[i-1]+read(); for(int i=1;i<=n;++i)f[i]=-1e18; /* for(int i=1;i<=n;++i) for(int j=0;j
             
              =count(s[t],i))t--; s[++t]=i; } printf("%lld\n",f[n]); return 0;}

转载于:https://www.cnblogs.com/cjyyb/p/7708356.html

你可能感兴趣的文章