JZOJ.3432 [GDOI 2014 시뮬레이션] 서버 문제 해결 보고서

5980 단어 동적 계획경사율 최적화

서버


제목의 대의.


우리는 n개의 서버에 파일을 복사해야 한다. 이 서버의 번호는 1, 2,..., n이다.우선, 우리는 일부 서버를 선택하여 파일을 그것들에 직접 복사할 수 있다.서버 i에 파일을 복사하려면 ci가 필요합니다.직접 복제를 통해 파일을 얻지 못한 서버에 대해 i+1, i+2,...서버 j(j의 파일은 직접 복제를 통해 얻은 것)를 찾을 때까지 순서대로 뒤로 검사합니다. 그래서 i는 j로부터 이 파일을 받았습니다. 비용은 j-i(j>i)입니다.또한 n의 파일은 직접 복사를 통해 얻어져야 한다. 왜냐하면 간접적으로 파일을 얻을 수 없기 때문이다.현재 모든 서버에서 파일을 얻을 수 있도록 최소 비용을 요구합니다.

형식 입력


입력 파일의 첫 줄에는 서버의 수를 나타내는 정수 n이 있습니다.입력 파일의 두 번째 줄에는 n개의 정수가 있고, 순수 i는ci를 표시하며, i 서버에서 파일을 직접 복제하는 비용을 표시합니다.

출력 형식


출력 파일에는 최소 비용이 드는 정수만 포함되어 있습니다.

샘플 입력


10 2 3 1 5 4 5 6 3 1 2

샘플 출력


십팔

데이터 범위


60%의 데이터 중, 1<=n<=1000 80%의 데이터 중, 1<=ci<=50 100%의 데이터 중, 1<=ci<=100000000, 1<=n<=1000000
최종 결과가 비교적 클 수 있으므로 적당한 데이터 형식을 선택하여 계산하는 것을 주의하십시오.

예제 설명


풀다


설정 Fi는 1~~i가 파일을 얻는 방식을 확정했고 서버 i가 직접 복사하는 방식을 선택하는 최소 비용을 표시합니다.정답은 Fn입니다.
이전 방정식은 Fi=Max(Fj+(i−j)∗(i−j−1)2)(0만약 어떤 최적화도 하지 않고 이 상태의 이동 방정식을 직접 하면 시간 복잡도 On2를 60분까지 닦을 수 있다.
100점에 대해 우리는 (i−j)∗(i−j−1)2라는 이전 비용은 두 번이고 한 번이면 좋으니 마음대로 단조로운 대열로 유지하면 된다. 이런 두 번의 비용 이전은 사율 최적화에 사용해야 한다.
가령 j에서 i로 옮기는 것이 k에서 i로 옮기는 것보다 낫다고 가정하면, (j양쪽 동승 2, 2 * Fj+(i−j)∗(i−j−1)<2 * Fk+(i−k)∗(i−k−1)
괄호를 뜯으면 2 * Fj + i2 + j2 - 2ij - i + j < 2 * Fk + i2 + k2 - 2ik - i + k
양쪽 동시에 빼기(i2-i)2*Fj+j2-2ij+j<2*Fk+k2-2ik+k
i가 포함된 항목을 모두 오른쪽으로 옮기고 i가 없는 항목을 모두 오른쪽으로 옮기면 2*(Fj-Fk)+j2-k2+j-k<2ij-2ik
양쪽을 동시에 제거(2j-2k),(2j-2k)<0

2∗(Fj−Fk)+j2−k2+j−k2j−2k > i


Gi=Fi+j2+j, Vi=2i를 설정하면 원래 부등식이

Gj−GkVj−Vk > i


왼쪽의 스타일을 자세히 살펴보면 어, 좀 익숙한 것 같지?

너는 잘못 보지 않았어, 그게 전설의 성투사 사율이야!


그래서 Gj−GkVj−Vk>i가 j에서 옮기는 것이 k에서 옮기는 것보다 낫다.반대로 Gj−GkVj−Vk우리는 단조로운 대열을 유지하는데, 대열에 인접한 두 원소의 경사율은 단조롭고 점차적으로 증가한다.우리가 i를 찾았을 때 팀의 머리 원소 l와 머리 뒤의 원소 p를 발견했고 gl−GpVl−Vp위의 식도 Gl−GpVl−VpFi의 할당을 마친 후, 우리는 i를 대열의 끝에 놓았다.이때 우리는 i가 옮겨오는 것이 팀 내의 다른 요소보다 더 좋을 수 있다는 것을 발견했고 우리는 팀 끝에서 앞으로 업데이트할 수 있었다.
함수 설정 kd(j,k) = Gj−GkVj−Vk, 대기열의 마지막 원소의 아래 표시는 r이며, 이 대기열은 d이다. 만약에 kd(dr−2,dr−1)>kd(dr−1,dr)라면dr−1은 반드시 최우선이 아니다. 폐기를 선언하고 대기열에서 차버릴 수 있다. 왜?

Reason One


수의 각도에서 해석하다.분류 토론<1> 만약 i>kd(dr−2,dr−1)>kd(dr−1,dr)라면dr−1은dr보다 우수하지 않다.<2> 만약 kd(dr−2,dr−1)>i>kd(dr−1,dr)라면dr−1은dr−2보다 우수하지 않다.<3>만약 kd(dr−2,dr−1)>kd(dr−1,dr)>i라면dr−1은dr−2보다 우수하지 않다.다시 말하면 어쨌든dr−1은 이 세 원소 중에서 가장 좋은 것이 아니라 군더더기이기 때문에 버려야 한다.

Reason Two


형의 각도에서 해석하다.kd(dr−2,dr−1)>kd(dr−1,dr)의 상황은 아래 그림과 같다
다음과 같은 상황은 대열의 두 원소 간의 경사율 단조성을 만족시키지 못하기 때문에dr−1을 제거한다. 이렇게 하면 새로 형성된 마지막 두 원소의 경사율은 원래의 마지막 두 원소의 경사율보다 크다. 이렇게 하면 경사율 단조성을 유지할 수 있다.
이것이 바로 사율 최적화의 전 과정이다. 각 요소에 대해 팀에 한 번 들어가고 한 번 나가기 때문에 총 시간의 복잡도는 O(n)로 100점을 받을 수 있다.

Code(Pascal)

var
    dl,c,f:array[0..1000000] of int64;
    n,j,k,l,i,o:longint;
function jl(o:int64):int64;
    begin
        exit(o*(o-1) div 2);
    end;
function min(a,b:int64):int64;
    begin
        if a<b then exit(a)
        else exit(b);
    end;
function ggg(j,k:int64):extended;
    begin
        exit((2*f[j]+j*j+j-2*f[k]-k*k-k)/(2*j-2*k));
    end;
begin
    readln(n);
    for i:=1 to n do
    read(c[i]);
    for i:=1 to n do
    f[i]:=jl(i)+c[i];
    dl[1]:=1;
    l:=1;
    o:=1;
    for i:=2 to n do
    begin
        while (O>L) AND (ggg(dl[l],dl[l+1])<i) do inc(l);
        f[i]:=min(f[i],f[dl[l]]+c[i]+jl(i-dl[l]));
        while (o>l) and (ggg(dl[o-1],dl[o])>ggg(dl[o],i)) do
        dec(o);
        inc(o);
        dl[o]:=i;
    end;
    writeln(f[n]);
end.
Python으로 이메일을 보내고 예약하는 방법
저장된 브라우저 자격 증명을 사용하는 자동 로그인 사용자

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage