11.06T1 DLZ常数剪枝+DP

#3878 最小值

描述

输入

第一行输入一个正整数 n和四个整数A,B,C,D 。

第二行输入 n个整数，第 i个数表示ai

输出

输出一行一个整数ans 表示答案。

样例输入[复制]

5 0 0 1 10
9 9 5 2 6

样例输出[复制]

提示

ST表优化区间最值查询，预处理Log数组O(1)查询对数，加上DLZ常数剪枝就可以过掉了

code：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 long long read(){
 6     long long x=0,f=1;
 7     char c=getchar();
 8     while(!isdigit(c)){
 9         if(c=='-')f=-1;
10         c=getchar();
11     }
12     while(isdigit(c)){
13         x=(x<<3)+(x<<1)+c-'0';
14         c=getchar();
15     }
16     return x*f;
17 }
18 long long a[500005];
19 long long n,A,B,C,D;
20 long long Function(long long a){
21     return A*a*a*a+B*a*a+C*a+D;
22 }
23 long long g[500005];
24 long long f[500005][30];
25 int Log[500006];
26 long long Ask(long long l,long long r){
27     long long k;
28     k=Log[r-l+1];
29     return min(f[l][k],f[r+1-(1<<k)][k]);
30 }
31 void pre(){
32     Log[1]=0;
33     for(int i=1;i<=16;i++){
34         Log[1<<i]=i;
35     }
36     for(int i=3;i<=500000;i++){
37         if(!Log[i])Log[i]=Log[i-1];
38     }
39 }
40 int main(){
41 //    freopen("min.in","r",stdin);
42 //    freopen("min.out","w",stdout);
43     pre();
44     n=read(),A=read(),B=read(),C=read(),D=read();
45     for(int i=1;i<=n;i++)a[i]=read();
46     for(int i=1;i<=n;i++)f[i][0]=a[i];
47     for(int j=1;j<=Log[n];j++)
48         for(int i=1;i+(1<<j)-1<=n;i++)
49             f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
50     for(int i=1;i<=n;i++)g[i]=-9999999999999;
51     g[0]=0;
52     for(int i=1;i<=n;i++){
53         for(int j=max(i-125,0);j<i;j++){
54             g[i]=max(g[i],g[j]+Function(Ask(j+1,i)));
55         }
56     }
57     cout<<g[n];
58     return 0;
59 }

over