[문제풀이] BZOJ 1010 장난감 포장 Toy

BZOJ 1010 장난감 포장 Toy
제목은Description P 교수가 올림픽을 보러 가려고 했지만 장난감을 아까워하지 않아 모든 장난감을 베이징으로 운반하기로 결정했다.그는 자신의 압축기를 사용하여 압축을 하는데, 그것은 임의의 물품을 한 무더기로 만들어 특수한 1차원 용기에 넣을 수 있다.P교수는 번호가 1...N인 N개의 장난감이 있는데 i번째 장난감은 압축을 거친 후 1차원 길이가 Ci로 변한다.정리를 편리하게 하기 위해서 P 교수는 1차원 용기에 있는 장난감의 번호가 연속적이어야 한다고 요구했다.또한 1차원 용기에 장난감이 여러 개 있다면 두 장난감 사이에 단위 길이의 충전재를 넣어야 한다. 형식적으로 i번 장난감을 j번 장난감에 한 용기에 넣으면 용기의 길이는 x=j-i+시그마(Ck)i<=K<=j 용기 제작 비용은 용기의 길이와 관련이 있다. 교수 연구에 따르면 용기의 길이가 x라면 제작비는 (X-L)^2.여기서 L은 상수입니다.P 교수는 용기의 수에 관심이 없어 임의의 길이의 용기를 만들 수 있고 심지어 L을 초과할 수도 있다.그는 비용이 가장 적기를 바란다.
설명 입력 Input Description 첫 번째 행에 두 개의 정수 N을 입력하고 L. 다음 N 행에 Ci를 입력합니다.
출력 설명 Output Description 출력 최소 비용
샘플 입력 Sample Input 5 4 3 2 1 4
샘플 출력 Sample Output 1
데이터 범위 및 프롬프트 Data Size & Hint 1<=N<=50000,1<=L,Ci<=10^7
분석:
상태 이동 방정식: (분명히)
dp[i]=min(dp[j]+(sum[i]−sum[j]+i−j−1−L)2) d p [ i ] = m i n ( d p [ j ] + ( s u m [ i ] − s u m [ j ] + i − j − 1 − L ) 2 )
sum s u m은 접두어 및
그리고 우리
f[i]=sum[i]+i,c=1+L f [ i ] = s u m [ i ] + i , c = 1 + L
원형은 다음과 같이 간략화할 수 있다.
dp[i]=min(dp[j]+(f[i]−f[j]−c)2) d p [ i ] = m i n ( d p [ j ] + ( f [ i ] − f [ j ] − c ) 2 )
여기
f, c f, c는 모두 미리 처리할 수 있는 것이다
1. 의사결정의 단조성을 증명한다
가령 현재 jj상태에서 kk상태보다 낫다고 가정한다(분명히 kk는 이전에 열거한 결정이다). 즉,
dp[j]+(f[i]−f[j]−c)2≤dp[k]+(f[i]−f[j]−c)2 d p [ j ] + ( f [ i ] − f [ j ] − c ) 2 ≤ d p [ k ] + ( f [ i ] − f [ j ] − c ) 2
그러면
i i 뒤에 상태
tt, 보증
kk에 공헌하지 않음(이미
j j 덮어쓰기)
증명이 필요합니다.
dp[j]+(f[t]−f[j]−c)2≤dp[k]+(f[t]−f[k]−c)2 d p [ j ] + ( f [ t ] − f [ j ] − c ) 2 ≤ d p [ k ] + ( f [ t ] − f [ k ] − c ) 2
... 에 의하여
f[i]=sum[i]+i f[i]=s um[i]+i, 따라서 단조로운 ()
sum s u m 및
ii 모두 단조로운 증가)
그래서
v=f[t]−f[i] v = f [ t ] − f [ i ]
기존 방식:
dp[j]+(f[i]+v−f[j]−c)2≤dp[k]+(f[i]+v−f[k]−c)2 d p [ j ] + ( f [ i ] + v − f [ j ] − c ) 2 ≤ d p [ k ] + ( f [ i ] + v − f [ k ] − c ) 2
변형↓ 가능한 한 기존의 형식을 뜯어내다
dp[j]+(f[i]−f[j]−c)2+2v∗(f[i]−f[j]−c)+4v2≤dp[k]+(f[i]−f[k]−c)2+2v∗(f[i]−f[k]−c)+4v2 d p [ j ] + ( f [ i ] − f [ j ] − c ) 2 + 2 v ∗ ( f [ i ] − f [ j ] − c ) + 4 v 2 ≤ d p [ k ] + ( f [ i ] − f [ k ] − c ) 2 + 2 v ∗ ( f [ i ] − f [ k ] − c ) + 4 v 2
이항
f[i]−f[j]−c≤f[i]−f[k]−c f [ i ] − f [ j ] − c ≤ f [ i ] − f [ k ] − c
f[j]≥f[k] f [ j ] ≥ f [ k ]
단조로운 점증성으로 매거 상태일 때
1 1 ~
i-3-1 i-3-1의 순서를 보증할 수 있다
f[j]≥f[k]f[j]≥f[k], 득증
2. 구사율 방정식
현재 의사 결정 i i 가 jj 상태에서 kk 상태보다 우수한 상태로 전환되면 다음과 같은 이점이 있습니다.
dp[j]+(f[i]−f[j]−c)2≤dp[k]+(f[i]−f[j]−c)2 d p [ j ] + ( f [ i ] − f [ j ] − c ) 2 ≤ d p [ k ] + ( f [ i ] − f [ j ] − c ) 2
확장, 변형, 필요:
dp[j]+f[i]2−2f[i]∗(f[j]+c)+(f[j]+c)2≤dp[k]+f[i]2−2f[i]∗(f[k]+c)+(f[k]+c)2 d p [ j ] + f [ i ] 2 − 2 f [ i ] ∗ ( f [ j ] + c ) + ( f [ j ] + c ) 2 ≤ d p [ k ] + f [ i ] 2 − 2 f [ i ] ∗ ( f [ k ] + c ) + ( f [ k ] + c ) 2
항목을 옮기다
j,k,j,k가 모여서:
(dp[j]+(f[j]+c)2)−(dp[k]+(f[k]+c)2)2∗(f[j]−f[k])≤f[i] ( d p [ j ] + ( f [ j ] + c ) 2 ) − ( d p [ k ] + ( f [ k ] + c ) 2 ) 2 ∗ ( f [ j ] − f [ k ] ) ≤ f [ i ]
왼쪽 부분은 경사율처럼 볼 수 있다.
Yj−YkXj−Xk Y j − Y k X j − X k
우리
슬로프
이것 괜찮아요?
Slope(k, j)≤f[i] S l o p e(k, j)≤ f[i]이면 설명
제이비
k우
3. 조직 알고리즘
그러면 현재 비교적 좋은 상태에 대해 우리는 대기열 qq를 만들어서 이 대기열을 유지한다. 우리는 다음과 같은 조작을 한다.

슬로프(q[l], q[l+1])≤f[i] S l o p e(q[l], q[l+1])≤f[i]이면 q[l] q[l]가 q[l+1] q[l+1]가 없으면 q[l] q[l] q[l] 삭제

슬로프(q[r-3.1], q[r])≥슬로프(q[r], i)S l o pe(q[r-3.1], q[r])≥S l o pe(q[r], i)일 경우 q[r]q[r]

를 삭제한다.
분석:
방정식이 성립될 때 jj가 k보다 우수한 충분한 필요조건이다. 만약에 우리가 지금 서열이 있다고 가정하면 팀의 머리는 현재 가장 좋은 것이다. 만약에 어떤 i값이 되면 팀의 첫 번째 p[l]p[l]와 팀의 첫 번째 p[l+1]p[l+1]에 대해 슬로프(q[l], q[l+1]))≤f[i]Slop(q[l]p], q[l+1])≤f[l+1]가 성립되면 q[l+l]가 [lq]보다 우수하고 [l]팀이 튀어나오기 때문에 [l+1]가 된다.안 될 때까지.
첫 번째 조작은 명백한데, 두 번째 조작은?하나의 상태를 서열에 넣을지 안 넣을지는 그것이 공헌을 할 수 있는지에 따라 결정된다. 즉, 팀의 우두머리가 될 수 있는지에 대한 가설은 우리가 현재 슬로프(q[a],q[a+1])≥슬로프(q[a+1],q[a+2])S l ope(q[a],q[a+1])≥S l ope(q[a+1],q[a+2])가 있다면 q[a+1]q[a+1]점은 팀의 우두머리가 될 수 밖에 없다.또한 Slope(q[a], q[a+1])≤f[i] S l o pe(q[a], q[a+1])≤f[i], q[a+1]q[a+1]가 q[a]q[a]보다 우수하기 때문에 q[a]q[a]를 팝업할 때 팀의 우두머리가 된다.그러나 이때 f[i]≥Slope(q[a], q[a+1])≥Slope(q[a+1], q[a+1], q[a+2]) f[i]≥S l o pe(q[a], q[a+1])≥S l o pe(q[a+1], q[a+2]), q[a[a+2]) [i][i]][a+2]도 q[a+1], q[a+1], q[a+1][a+1]보다 우수해야 하므로 [a+1][a+1]를 [a+1]+1][a+1]+1]로 팝업하면 어떻게 되든 [a+1][+1][a+1][+1][a+1][+공헌 유추를 해보겠습니다. 저희가 팀 끝만 조작할 때,만약에 그 경사율 Slope(q[r-3-1], q[r])≥Slope(q[r], i)S l o pe(q[r-3] 1], q[r])≥S l o pe(q[r], i))를 직접 팝업하면 q[r] q[r]를 바로 팝업하면 우리의 이 조작 후에 경사율이 단조롭게 증가하는 것을 보장할 수 있다. 즉, 상철포를 유지하는 것이 경사율 최적화다!
스스로 매우 상세하다고 여기니, 문제가 있으면 아래에 메시지를 남겨도 됩니다!
Code:

#include 
using namespace std;
#define ll long long
ll n,L;
ll f[50005];
ll dp[50005];
ll q[50005];
ll head,tail; 
ll read() {
    ll ans=0,flag=1;
    char ch=getchar();
    while((ch<'0'||ch>'9') && ch!='-') ch=getchar();
    if(ch=='-') flag=-1,ch=getchar();
    while(ch>='0' && ch<='9') ans=ans*10+ch-'0',ch=getchar();
    return ans*flag;
}
double slope(ll k,ll j) {return (double) (dp[j]-dp[k]+(f[j]+L)*(f[j]+L)-(f[k]+L)*(f[k]+L))/(2.0*(f[j]-f[k]));}
int main() {
    n=read(),L=read();
    L++;
    for(int i=1;i<=n;i++) {
        ll a=read();
        f[i]=f[i-1]+a+1;
    }
    for(int i=1;i<=n;i++) {
        while(head1])<=f[i]) head++;
        int t=q[head];
        dp[i]=dp[t]+(f[i]-f[t]-L)*(f[i]-f[t]-L);
        while(head1],q[tail])) tail--;
        q[++tail]=i;
    } 
    printf("%lld",dp[n]);
}