[JZOJ 3432][OnlineJudge 1061] SM 서버(사율 최적화 해석 포함)

4382 단어 dp경사율 최적화

Description


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

Solution


우선 이 문제의 60점 방법은 매우 간단하고fi로만 i번째 필수 선택의 최소 대가를 표시한다.우리는 경사율 최적화를 고려하여 현재 i를 설정하면 상태 j가 k보다 우수하다(j가 앞에 있다).
fj+(j−i)∗(j−i−1)2항목 이동:
fj−fk+j2−k2−j+k2j−kg(j,k)로 이 물건을 표시하고 경사율 최적화 DP를 하면 된다.
복잡도:
O(2n) ;
여기에 경사율 최적화에 대해 설명합니다.

경사율 최적화


경사율 최적화 g 함수는 단조로운 것을 만족시킬 수 있고 앞의 것이 뒤의 것보다 낫다. 본제를 예로 들면 대열의 요소는 j1, j2, j3,...,있다: (이것은 명백하다)
i>g(j1,j2),i>g(j2,j3),i>g(j3,j4)...
다음과 같은 기능도 있습니다.
i>g(j1,j2)>g(j2,j3)>g(j3,j4)>...
설명은 다음과 같습니다. 인접한 세 요소를 가정합니다.
j1,j2,j3 ,
이상의 양식을 보증하려면 반드시
g(j1, j2)j2 ,
왜냐하면
j2가 가장 우수하다면:
g(j1,j2)>i
g(j2,j3)g(j2,j3)위의 가설과 충돌하기 때문에 가설이 성립되지 않고
그래서
g(j1, j2)j2 ,
그래서 전체적인 만족:
i>g(j1,j2)>g(j2,j3)>g(j3,j4)>...

Code

#include<cstdio>
#include<cstdlib>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(LL i=a;i>=b;i--)
using namespace std;
typedef long long LL;
const int N=1000500;
int read(int &n)
{
    char ch=' ';int q=0,w=1;
    for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
    if(ch=='-')w=-1,ch=getchar();
    for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n;
}
int n;
int a[N],S,T;
LL f[N],d[N];
double G(LL i,LL j){return(1.0*(f[i]-f[j]+(i*i-j*j-i+j)/2)/(i-j));} 
int main()
{
    read(n);
    fo(i,1,n) read(a[i]);
    f[n]=a[n];d[S=T=1]=n;
    fod(i,n-1,0)
    {
        while(T>S&&G(d[S],d[S+1])>i)S++;
        f[i]=(d[S]-i)*(d[S]-i-1)/2+f[d[S]]+a[i];
        while(T>S&&G(d[T-1],d[T])<G(d[T],i))T--;
        d[++T]=i;
    }
    printf("%lld
",f[0]);
    return 0;
}
JavaScript API 자동화 테스트 - 사용할 라이브러리/프레임워크는 무엇입니까?
TypeScript(JavaScript)로 Array 분할

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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