[HNOI2008] 玩具装箱 题解

很难得遇到细节题
打码5分钟调试两小时
感谢游老师送出的1.5h调试，感激
(争取每天用我的代码训练老师的该题能力）
细节/思路见注释

#include <bits/stdc++.h>
#define int long long
using namespace std;
/*
本题细节很多！！！

1.注意要把‘0’放进去，否则'1'一直弹不出去，导致答案偏大
2.放了'0‘以后，注意初始化，例如h[0]=L+1;同理，’0‘在坐标轴上也是，如g[0]
3.我这个代码有点绕，有用数组，也有用函数值，注意这两个都要赋值
最后感谢游老师1h送出的调试AC 

f[i]=min_j(f[j]+(i-j-1+sum[i]-sum[j]-L)^2)
i和j提出来给函数
g[i]=sumi+i;
h[i]=i+sum[i]+L+1

再拆开：=min_j(f[j]+(g[i]-h[j])^2)=min_j(g[i]*g[i]+h[j]*h[j]+f[j]-2*g[i]*h[j])
斜率优化公式中
a[i]=-2*g[i]，b[j]=h[j]，c[i]=g[i]*g[i]，d[j]=h[j]*h[j]+f[j]
坐标（bj,-dj)
fi=ci- b,b是我线性规划要求的
显然横坐标递增（bi)
k则是递减(ai)


*/
int sum[50005];
int g[50005], h[50005], cost[50005];
int k[50005];
int a[50005], b[50005], c[50005], d[50005];
int dp[50005];

struct node {
    int xx;
    int yy;
    int id;
};
node Q[400005];
bool check(node x, node y, int z) {  //队首，次级队首，末尾,肯定是整数
    double k1 = 1.0 * (y.yy - x.yy) / (y.xx - x.xx);
    //cout<<x.id<<' '<<y.id<<' ' <<k1<<' '<<z<<endl;
    if (k1 >= z) {  //前者偏大
        return 1;
    } else {
        return 0;
    }
}
bool checkdot(node x, node y, node z) {  //队首，次级队首，末尾,肯定是整数
    double k1 = 1.0 * (y.yy - x.yy) / (y.xx - x.xx);
    double k2 = 1.0 * (z.yy - y.yy) / (z.xx - y.xx);
    if (k1 > k2) {  //前者偏大 ,成立
        return 1;
    } else {
        return 0;
    }
}
deque<node> q;
signed main() {
    //ios::sync_with_stdio(false);
    int n, L;
    cin >> n >> L;
    for (int i = 1; i <= n; i++) {
        cin >> cost[i];
        sum[i] = sum[i - 1] + cost[i];
    }
    h[0]=L+1;
    for (int i = 1; i <= n; i++) {
        g[i] = i + sum[i];
        h[i] = i + sum[i] + L + 1;

        a[i] = 2 * g[i] * (-1);

        c[i] = g[i] * g[i];
        //
        //		b[i]=h[i];
        //		d[i]=h[i]*h[i];
    }
    int head = 1;
    int tail = 1;
    //dp[1] = (cost[1] - L) * (cost[1] - L);
    Q[head] = (node){ L+1, -(L+1)*(L+1), 0 };
    for (int i = 1; i <= n; i++) {
        while (head < tail && check(Q[head], Q[head + 1], a[i])) {
            ++head;
        }
        int j = Q[head].id;
        dp[i] = (a[i] * h[j] + c[i] + h[j] * h[j] + dp[j]);
        //cout<<j<<endl;
        node now = (node){ h[i], -(h[i] * h[i] + dp[i]), i };
        while (head < tail && checkdot(Q[tail - 1], Q[tail], now) == 0) --tail;
        Q[++tail] = now;
        /*if(i<=10) {
        	for(int jj=head;jj<=tail;++jj)
				cout<<Q[jj].xx<<' '<<Q[jj].yy<<' '<<Q[jj].id<<endl;
			//cout<<dp[1]<<' '<<h[1]<<endl;
			//cout<<endl;
			
		}*/
    }
    cout << dp[n] << endl;
}