APIO2010 特别行动队-白红宇

APIO2010 特别行动队

阅读量：7199 次

发布时间：2019-06-29

本文共 2590 字，大约阅读时间需要 8 分钟。

P2407 - 【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。

Source

APIO，斜率优化，动态规划

简单方程斜率优化，dp[i]=max(dp[j] + a*(C[i]-C[j])^2 + b*(C[i]-C[j])+c);最关键的一点，除法有精度差！！！！！！，ｇｅｔｘ（）函数修改为ｃａｌｅ（

l1,l2,l3）函数，相乘计算，不用除法：

1 #include
      
        2 //#include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
               10 #include
               
                11 #include
                12 #include
                 
                  13 #define ll long long14 #define inf 1<<3015 #define rep(i,a,b) for(register int i=a;i<=b;++i)16 #define re register17 using namespace std;18 const int N=1000011;19 ll C[N],dp[N],a,b,c;20 int q[N];21 int n;22 inline ll gi( )23 {24 register ll ret=0,f=1;char ch=getchar();25 while((ch<'0'||ch>'9')&&(ch!='-')) ch=getchar();26 if(ch=='-') f=-1,ch=getchar();27 while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();28 return ret*f;29 }30 inline ll getnum(int i,int k) {31 register ll u=C[i]-C[k];32 return dp[k]+a*u*u+b*u+c;33 }34 inline bool cale(int l1,int l2,int l3) {35 register ll b1=dp[l1]+a*C[l1]*C[l1]-b*C[l1],b2=dp[l2]+a*C[l2]*C[l2]-b*C[l2],b3=dp[l3]+a*C[l3]*C[l3]-b*C[l3];36 register ll k1=-2*a*C[l1],k2=-2*a*C[l2],k3=-2*a*C[l3];37 return (b3-b2)*(k1-k2) <= (b2-b1) * (k2-k3);// ¾«¶È²î¿ÓÁËÎÒ£¡£¡£¡ 38 }39 int main( )40 {41 n=gi();a=gi(),b=gi(),c=gi();42 rep(i,1,n) C[i]=gi(),C[i]+=C[i-1];43 q[0]=0;44 q[1]=1;45 dp[0]=0;46 dp[1]=a*C[1]*C[1]+b*C[1]+c;47 register int hd=0,tl=1;48 rep(i,2,n) {49 while(hd+2<=tl&&cale(q[tl-2],q[tl-1],q[tl])) q[tl-1]=q[tl--];// bug <= 50 while(hd
                  
                   <=getnum(i,q[hd+1])) hd++;51 dp[i]=getnum(i,q[hd]);52 q[++tl]=i;53 }54 printf("%lld",dp[n]);55 return 0;56 }

转载于:https://www.cnblogs.com/ypz999/p/6702069.html

你可能感兴趣的文章