斜率优化板子 玩具装箱
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n = 0 , L = 0 , l = 1 , r = 0;
array<int , 500100> val , pre , dp , que;
//#define X(id) pre[id]
//#define Y(id) dp[id] + (pre[id] + L) * (pre[id] + L)
inline int X(int id)
{
return pre[id];
}
inline int Y(int id)
{
return dp[id] + (pre[id] + L) * (pre[id] + L);
}
inline long double slope(int a , int b)
{
return (long double)((Y(b) - Y(a)) / (X(b) - X(a)));
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
cin >> n >> L;
++ L;
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
for(int i = 1;i <= n;++ i)
{
cin >> val[i];
pre[i] = pre[i - 1] + val[i] + 1;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
que[++ r] = 0;
for(int i = 1;i <= n;++ i)
{
while(l < r && slope(que[l] , que[l + 1]) <= 2 * pre[i]) ++ l;
int nxt = que[l];
dp[i] = dp[nxt] + (pre[i] - pre[nxt] - L) * (pre[i] - pre[nxt] - L);
while(l < r && slope(que[r - 1] , que[r]) >= slope(que[r - 1] , i)) -- r;
que[++ r] = i;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
cout << dp[n] << endl;
return 0;
}
6~15行那里为什么用宏定义全错,用函数就对了呢?