P3195 [HNOI2008] 玩具装箱
\(dp_i\) 表示前 \(i\) 个玩具的最小代价。
\(s_i=\sum_{j\le i} c_i+1\)。
设 \(L'=L+1\)。
\(dp_i=\min_{j<i}\{dp_j+(s_i-s_j-L')^2\}\)
\(dp_i-s_i'^2+2s_iL'=\min_{j<i}\{dp_j+(s_j'+L)^2-2s_is_j\}\)
\(b=y-kx\)
\(k\) 与 \(i\) 有关,对于 \(k_i\),我们要找出一条过点 \((x,y)\) 的斜率为 \(k_i\) 的直线使得直线的截距最小,显然是凸包上的切点,而且是下凸包。因此我们维护下凸包。
因为 \(x\) 单调递增,用单调队列维护下凸包。因为 \(k\) 也是单调递增的,因此我们直接取合法的队首。
Code
#include<bits/stdc++.h>
// #define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
using namespace std;
typedef long long ll;
typedef long double ld;
const int N=5e4+6;
int c[N];
int n,L;
ll dp[N];
ll s[N];
struct node{
ll x,y;
};
node que[N];
int l,r;
ld cal(node a,node b){
return 1.0*(b.y-a.y)/(b.x-a.x);
}
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("my.out","w",stdout);
#endif
sf("%d%d",&n,&L);
rep(i,1,n) {
sf("%d",&c[i]);
s[i]=c[i]+s[i-1];
}
rep(i,1,n) s[i]+=i;
L++;
l=r=1;
que[1]={0,1ll*L*L};
rep(i,1,n){
ld k=2*s[i];
while(l<r&&k>=cal(que[l],que[l+1])){l++;}
ll b=que[l].y-k*que[l].x;
dp[i]=b+s[i]*s[i]-2*s[i]*L;
ll x=s[i],y=dp[i]+(s[i]+L)*(s[i]+L);
while(r>l&&cal({x,y},que[r])<=cal(que[r],que[r-1])) r--;
que[++r]={x,y};
// printf("%lld\n",dp[i]);
}
pf("%lld\n",dp[n]);
}
标签:P3195,que,HNOI2008,装箱,dp,define
From: https://www.cnblogs.com/liyixin0514/p/18435498