[JZOJ 3432] 서버(사율 최적화 DP FAQ & 상세 답변)

4218 단어 dp단조로운 대열기울기 최적화 DP정책 결정의 단조성

Description


우리는 하나의 파일을 n개의 서버에 복사해야 한다. 이 서버의 번호는 S1, S2,..., Sn이다.우선, 우리는 일부 서버를 선택하여 파일을 그것들에 직접 복사할 수 있다.파일을 서버 Si에 복사하려면 ci > 0의 설치 비용이 필요합니다.직접 복사된 파일이 없는 서버 Si의 경우 Si+1, Si+2를 차례로 뒤로... 서버 Sj: Sj의 파일을 찾을 때까지 직접 복사해서 얻을 수 있습니다. 그래서 Si는 Sj로부터 이 파일을 간접적으로 복사합니다. 이런 복사 방식의 읽기 비용은 j-i(주의 j>i)입니다.또한 Sn의 파일은 다른 서버를 통해 간접적으로 복사할 수 없기 때문에 직접 복사를 통해 복사해야 합니다.우리는 모든 서버에 대해 직접 또는 간접적인 방식으로 복제하는지 확인하는 복제 방안을 설계했다. (Sn은 직접 방식만 사용할 수 있음) 최종적으로 모든 서버에서 파일을 얻을 수 있고 총 비용이 가장 적게 든다.
100% 데이터 중 1 <= n <= 1000000, 1 <=ci <= 1000000

Analysis


시합할 때 내가 치는 2차원 dp는 많은 사람들이 1차원적이며, 1차원을 쳐야 정해인 사율 최적화를 생각할 수 있다.1년 동안 경사율이 최적화되지 않아서 QAQ를 잊어버리고 얼른 악보했어요.알겠습니다. 1차원 dp식은 f[i]=min(f[j]+(j−i)∗(j−i−1)2+a[i])입니다. j>i이렇게 하면 O(n2)의, TLE입니다.현재의 i(i는 뒤에서 앞으로 일일이 열거하는 것)에 대해 두 가지 결정 j,k,j가 k보다 우수하면 만족해야 할 조건은
f[j]+(j−i)∗(j−i−1)2+a[i]항목을 옮기다
f[j]−f[k]+j2−k2−j+k2j−k설치하다
g(j,k)는 부등식 왼쪽을 나타낸다.
그래서 우리는 단조롭고 점차 줄어드는 대열을 유지하고 있는데, 그 안은 아마 이렇게 생겼을 것이다
i>g(jl,jl+1)>g(jl+1,jl+2)>⋯>g(jr−1,jr)
대열의 우두머리.
jl은 현재
i의 최우해.
그리고 우리
i는 점차 줄어드는 것이기 때문에 일단
i이것 때문에
jl은 더 이상 최우선이 아니다.
현재의
i 다음에 대기열에 추가합니다.
하면, 만약, 만약...
g(jr−1,jr)jr는 영원히 최우선을 얻을 수 없습니다. 증명은 다음과 같습니다.
반증법 을 채택하여 가설 하다
jr가 가장 좋은 것을 얻을 수 있다면,
jr가 우수하다
jr−1은
g(jr−1,jr)>i ,
jr가 우수하다
i는
g(jr,i)위의 두 부등식을 종합하면
g(jr,i)놀랍게도 부등식에 모순이 생겼다!
증명하다
그래서
jr는 상술한 조건이 충족되지 않을 때까지 차버리고
i 입대.
그러나naive의 나는 일찍이 이런 의문이 있었는데, 왜 직접 사용할 수 없는지
g(i,jr) 즉
보다 우수하다
jr가 팀 끝의 출전 상황을 판단할까요?
현재
보다 우수하다
jr는 결코 이후의 것을 대표하지 않는다
i도 우수하다
jr.
그래, 사율 최적화 dp는 왜 이 이름을 지었지?... 때문에
g(j,k) 이 물건은 평면도에서 매우 닮았다
j, k 두 시의 사율!
이 그림은 직관적이죠.

Code

#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int N=1000010;
int n;
ll f[N],q[N],a[N];
double G(ll j,ll k)
{
    return (f[j]-f[k]+(j*j-k*k-j+k)/2.0)*1.0/(j-k);
}
int main()
{
    scanf("%d",&n);
    fo(i,1,n) scanf("%lld",&a[i]);
    f[n]=a[n];
    int l=1,r=1;
    q[1]=n;
    fd(i,n-1,0)
    {
        while(l<r && i<G(q[l],q[l+1])) l++;
        f[i]=f[q[l]]+a[i]+(q[l]-i)*(q[l]-i-1)/2;
        while(l<r && G(q[r-1],q[r])<G(i,q[r])) r--;
        q[++r]=i;
    }
    printf("%lld",f[0]);
}
서버 select 모델
Socket 프로그래밍 ----- 아날로그 QQ 채팅(TCP)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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