bzoj1010 장난감 포장 [결정 단조성 최적화 dp]

하나의 모범 문제라고 할 수 있다.우리는 먼저 소박한 dp방정식을 얻을 수 있다. f[i]=min(f[j]+w(j,i)),j∈[0,i). w(j,i)는 j+1~i를 포장하여 운송하는 비용의 시간 복잡도는 O(n2)라고 표시한다. 그리고 표를 작성하면 의사결정의 단조성을 만족시킬 수 있기 때문에 단조로운 대기열로 의사결정점을 유지하고 2분의 1을 의사결정점으로 하는 구간을 찾으면 된다. 시간의 복잡도는 O(nlogn)이다. 일일이 열거할 때 j+1이 j보다 더 좋은 방식으로 의사결정점을 이동하는지 직접 판단할 수 없다. 예를 들어 다음과 같다.

f[0]=0;head=1;q[++tail]=0;
for(int i=1;i<=n;i++)
{
   while(headq[head+1]，i)q[head]，i))
       head++;
   f[i]=calc(q[head],i);
   q[++tail]=i;
}

뒤의 결정 지점의 결정 범위가 앞의 결정 지점의 결정 범위를 전체적으로 덮어쓰는 경우가 있기 때문이다. 예를 들어 11111111111111111111122222222222222222222222222222222가 결정 지점 3에 가입한 후: 1111111111111111111111111111111111111113333333333333333은 중간 단락 1에서 오류가 발생할 수 있다.그러니까 꼭 2점.

#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
using namespace std;

int getint() 
{
    int i=0,f=1;char c;
    for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
    if(c=='-')c=getchar(),f=-1;
    for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';
    return i*f;
}

const int N=50005;
struct node
{
    int l,r,p;
}q[N];
int n,L;
ll sum[N],f[N];

ll calc(int j,int i)
{
    return f[j]+(i-(j+1)+sum[i]-sum[j]-L)*(i-(j+1)+sum[i]-sum[j]-L);
}

int find(node t,int x)
{
    int l=t.l,r=t.r;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(calc(x,mid)1;
        else l=mid+1;
    }
    return l;
}
void dp()
{
    int head=1,tail=0;
    q[++tail]=(node){0,n,0};
    for(int i=1;i<=n;i++)
    {
        if(i>q[head].r)head++;
        f[i]=calc(q[head].p,i);
        if(calc(i,n)q[tail].p,n))
        {
            while(head<=tail&&calc(i,q[tail].l)q[tail].p,q[tail].l))
                tail--;
            if(head<=tail)
            {
                int p=find(q[tail],i);
                q[tail].r=p-1;
                q[++tail]=(node){p,n,i};
            }
            else q[++tail]=(node){i,n,i};
        }
    }
}

int main()
{
    //freopen("lx.in","r",stdin);
    //freopen("lx.out","w",stdout);
    n=getint(),L=getint();
    for(int i=1;i<=n;i++)
        sum[i]=getint()+sum[i-1];
    dp();
    cout<return 0;
}