[APIO2010 commando]斜率优化1D/1D方程、动态规划

【题目地址】http://www.apio.olympiad.org/
【算法分析】
易得方程F[i]=F[j]+g(Si-Sj)  g为那个二次函数。
然后列不等式F[j]+g(Si-Sj)变形得(F[j]-F[k]+a*(Sum[j]*Sum[j]-Sum[k]*Sum[k])+b*(Sum[k]-Sum[j])) / ((Sum[j]-Sum[k])*a*2) <=Si。
然后这就是经典的斜率优化dp。
【CODE】
#include #include #include #include using namespace std;
typedef long long lld;
const int N=1000005;
const lld INF=(lld)(1)<<60;
int n,a,b,c;
int xl[N],Q[N];
lld Sum[N],F[N];
char ch;
bool fu;

void Read(int &x){
ch=getchar();
while (!(ch>=’0′ && ch<='9' || ch=='-')) ch=getchar();
x=0;
fu=false;
if (ch==’-‘){
fu=true;
ch=getchar();
}
while (ch>=’0′ && ch<='9'){
x=x*10+ch-‘0’;
ch=getchar();
}
if (fu) x=-x;
}

void input(){
Read(n);
Read(a); Read(b); Read(c);
for (int i=1;i<=n;i++)
Read(xl[i]);
Sum[0]=0;
for (int i=1;i<=n;i++)
Sum[i]=Sum[i-1]+xl[i];
}

inline lld g(lld x){return x*x*a+x*b+c;}
inline lld pos(int j,int k){
return (F[j]-F[k]+a*(Sum[j]*Sum[j]-Sum[k]*Sum[k])+b*(Sum[k]-Sum[j]))/
((Sum[j]-Sum[k])*a);
}

void work(){
int i,j,h,t;
h=t=1; Q[1]=0;
F[0]=0;
for (i=1;i<=n;i++) F[i]=-INF;
for (i=1;i<=n;i++){
while (h F[i]=F[Q[h]]+g(Sum[i]-Sum[Q[h]]);
while (h t++;
Q[t]=i;
}
cout << F[n] << endl;
}

int main(){
freopen("commando.in","r",stdin);
freopen("commando.out","w",stdout);
input();
work();
}