很难得遇到细节题
打码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;
}