[HYBZ 1010]斜率优化的动态规划

【题目】

http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1010

【算法分析】

好不容易终于看懂了，我还是链接一下算了。。。

http://www.byvoid.com/blog/noi-2009-poet/

模仿他的解法三即可。。。

【CODE】

#include #include #include #include #define sqr(x) ((x)*(x))
using namespace std;
const int N=60000;
int n,L,head,tail,a[N],qp[N];
long long qf[N],f[N],sum[N];

void init(){
     scanf("%d%d",&n,&L);
     for (int i=1;i<=n;i++){
         scanf("%d",&a[i]);
         a[i]++;
     }
     sum[0]=0;
     for (int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
}

double xl(int i,int j){
       return (f[j]+sqr(sum[j])-f[i]-sqr(sum[i]))/(sum[j]-sum[i]);
}

void work(){
     f[0]=0;
     int head=1, tail=1;
     qf[1]=0; qp[1]=0;
     for (int i=1;i<=n;i++){
         while (head         int &j=qp[head];
         f[i]=f[j]+sqr(sum[i]-sum[j]-1-L);
         while (head         tail++;
         qp[tail]=i;
         qf[tail]=f[i];
     }
     cout << f[n] << endl;
}

int main(){
    init();
    work();
}