기울 기 최적화 DP

지금 은 저녁 0 시 30 분 입 니 다. 제 가 이 글 을 쓰 고 오늘 배 운 간단 한 기울 임 률 최적화 를 정리 하 겠 습 니 다.
경사 율 최적화 란 무엇 입 니까? 바로 전달 식 을 y = kx + b 로 쓰 는 형식 입 니 다.
원래 의 푸 시 방식 이 이렇게 길다 고 가정 합 니 다: f [i] = min {f [j] + C}. 그 중에서 C 는 i 에 관 한 함수 일 수 있 습 니 다. j 에 관 한 함수 일 수도 있 고 i 와 j 에 관 한 함수 일 수도 있 습 니 다.
앞의 두 가지 상황 은 단조 로 운 대기 열 을 통 해 해결 할 수 있 지만 상황 3 에서 i 와 j 를 분리 할 수 없고 경사 율 최적화 만 사용 할 수 있 습 니 다.
y = kx + b, 그 중에서 y = f (j), k = f (i), x = f (j), b = f (i) + const, 그 중에서 f (x) 는 x 와 관련 된 함 수 를 대표 합 니 다.
텅 비 었 다 고 만 말 하고 우 리 는 구체 적 으로 분석 했다.
예제 1: HDU 3507 Print Article
사이트 주소:http://acm.hdu.edu.cn/showproblem.php?pid=3507
전달 식 f [i] = min {f [j] + (sum [i] - sum [j]) ^ 2 + m} 을 얻 기 어렵 지 않 습 니 다.
min 함 수 를 제거 하고 펼 치기: f [i] = f [j] + sum [i] ^ 2 - 2 * sum [i] * sum [j] + sum [j] ^ 2 + m
i 를 포함 하 는 항목 과 j 를 포함 하 는 항목 을 분리 하고 단순히 j 를 포함 하 는 항목 을 왼쪽 에 쓰 십시오: f [j] + sum [j] ^ 2 = 2 * sum [i] * sum [j] + f [i] - sum [i] ^ 2 - m
이제 f [j] + sum [j] ^ 2 를 y 로 보고 2 * sum [i] 을 k 로 보고 sum [j] 을 x 로 보고 f [i] - sum [i] ^ 2 - m 를 b 로 본다.
모든 점 (sum [j], f [j] + sum [j] ^ 2) 은 고정 되 어 있 으 며, 모든 i 에 대해 서 는 경사 율 2 * sum [i] 도 고정 되 어 있 으 며, 절 거 리 는 b 입 니 다.
b. 작 을 수록 f [i] 가 작 아 집 니 다.우 리 는 이미지 적 으로 2 * sum [i] 의 선 이 아래 에서 위로 쓸 리 고 쓸 리 는 첫 번 째 점 이 바로 답 이 라 고 이해 할 수 있다.
우 리 는 두 점 사이 의 경사 율 을 유지 하기 위해 대열 을 만 들 었 다.경사 율 이 단조 로 운 증 가 를 보장 할 수 있다 면 첫 번 째 만족 경사 율 이 2 * sum [i] 보다 큰 것 이 결과 입 니 다.
2 * sum [i] 도 단조 로 워 서 팀 을 나 갈 수 있 습 니 다.시간 복잡 도 N.
#include
using namespace std;
#define int long long
const int maxn=500000+10;
int n,m,x,s[maxn],f[maxn],q[maxn];
int yval(int x,int y){
    return f[y]-f[x]+s[y]*s[y]-s[x]*s[x];
}//  y    
int xval(int x,int y){
    return s[y]-s[x];
}//  x    
signed main(){
    while(cin>>n>>m){
        for(int i=1;i<=n;i++){
            scanf("%lld",&x);
            s[i]=s[i-1]+x;
        }
        memset(f,0x3f,sizeof(f));
        memset(q,0,sizeof(q));
        int l=1,r=1;
        q[l]=0,f[0]=0;
        for(int i=1;i<=n;i++){
            while(l1])<=xval(q[l],q[l+1])*2*s[i])l++;
　　　　　　　//              ，   
            f[i]=f[q[l]]+(s[i]-s[q[l]])*(s[i]-s[q[l]])+m;
　　　　　　　//  f[i]
            while(l1],q[r])*xval(q[r],i)>=xval(q[r-1],q[r])*yval(q[r],i))r--;
　　　　　　　//         ，   
            q[++r]=i;
        }
        printf("%lld
",f[n]);
    }
    return 0;
}

예제 2: P3195 [HNOI 2008] 장난감 포장 TOY / 【 템 플 릿 】 경사 율 최적화
사이트 주소:https://www.luogu.com.cn/problem/P3195
 
푸 시 방정식 을 내 놓 는 것 은 어렵 지 않다.
dp[i]=min{dp[j]+(sum[i]+i−sum[j]−j−L−1)^2}
 
A = i + sum [i], B = j + sum [j] + 1 을 설정 해도 무방 하 다.푸 시 방식 은 dp [i] = min {dp [j] + (A - B + L) ^ 2} 로 전환 할 수 있 습 니 다.
 
다음 부분 은 독자 에 게 남 겨 두 고 스스로 무 너 뜨 린 다.
 
코드 보기:
#include
using namespace std;
#define int long long
const int maxn=100000;
int n,L,f[maxn],q[maxn];
int c[maxn],sum[maxn];
int a(int i){
    return i+sum[i];
}
int b(int i){
    return i+sum[i]+1;
}
int x(int i,int j){
    return b(j)-b(i);
}
int y(int i,int j){
    return f[j]+b(j)*b(j)-f[i]-b(i)*b(i);
}
signed main(){
    cin>>n>>L;
    for(int i=1;i<=n;i++){
        scanf("%lld",&c[i]);
        sum[i]=sum[i-1]+c[i];
    }
    memset(f,0x3f,sizeof(f));
    int l=1,r=1;
    q[l]=0;f[0]=0;
    for(int i=1;i<=n;i++){
        while(l1])<=x(q[l],q[l+1])*2*(a(i)-L))l++;
        f[i]=f[q[l]]+(a(i)-b(q[l])-L)*(a(i)-b(q[l])-L);
        while(l1],q[r])*x(q[r],i)>=x(q[r-1],q[r])*y(q[r],i))r--;
        q[++r]=i;
    }
    cout<endl;
    return 0;
}

예제 3: P2120 [ZJOI 2007] 창고 건설
사이트 주소:https://www.luogu.com.cn/problem/P2120
우리 가 가장 낮은 점, 즉 n 번 째 점 에 창 고 를 건설 해 야 한 다 는 것 을 쉽게 생각 할 수 있다.이 를 통 해 f [i] 는 1 ~ i 공장 의 최소 비용 만 처리 하 겠 다 고 밝 혔 다.
j 를 찾 았 습 니 다.
두 개의 접두사 와 sp 를 p 로 하 는 접두사 와 spx 를 p * x 로 하 는 접두사 와 미리 처리 합 니 다.
간략화 된 N ^ 2 의 상 전 방정식 을 내 놓 을 수 있 습 니 다: f [i] = min {f [j] + c [i] + x [i] * (sp [i - 1] - sp [j]) - spx [i - 1] + spx [j]}
함수 형식 으로 쓰기: f [j] + spx [j] = x [i] * sp [j] + f [i] - c [i] - x [i] * sp [i - 1] + spx [i - 1], 그 중 y = f [j] + spx [j], k = x [i], x = sp [j], b = f [i] - c [i] - x [i] * sp [i - 1] + spx [i - 1]
데이터 가 x [i] 단조 로 운 증 가 를 보장 합 니 다. 아주 좋 습 니 다!!!
코드 보기:
#include
using namespace std;
#define int long long
const int maxn=1000000+10;
int c[maxn],x[maxn],p[maxn],q[maxn];
int sp[maxn],spx[maxn],f[maxn],n;
inline int yval(int a,int b){
    return f[b]-f[a]+spx[b]-spx[a];
}
inline int xval(int a,int b){
    return sp[b]-sp[a];
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%lld%lld%lld",&x[i],&p[i],&c[i]);
        sp[i]=sp[i-1]+p[i];
        spx[i]=spx[i-1]+p[i]*x[i];
    }
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    int l=1,r=1;
    q[l]=0;
    for(int i=1;i<=n;i++){
        while(l1])<=xval(q[l],q[l+1])*x[i])l++;
        f[i]=f[q[l]]+c[i]+x[i]*(sp[i-1]-sp[q[l]])-spx[i-1]+spx[q[l]];
        while(l1],q[r])*xval(q[r],i)>=xval(q[r-1],q[r])*yval(q[r],i))r--;
        q[++r]=i;
    }
    printf("%lld
",f[n]);
    return 0;
}

 
예제 4: P3628 [APIO 2010] 특별 행동 팀
사이트 주소:https://www.luogu.com.cn/problem/P3628
이 문 제 는 앞 처럼 그렇게 딱딱 하지 않다. 적어도 나 는 그것 이 판자 라 고 생각 하지 않 는 다.
내 놓 은 방정식 은 이렇게 생 겼 다. f [j] + a * sum [j] ^ 2 - b * sum [j] = (2 * a * sum [i]) * sum [j] + f [i] - a * sum [i] ^ 2 - b * sum [i] - c
데이터 범 위 를 보 세 요. a 항 은 마이너스 입 니 다. 이때 경사 율 2 * a * sum [i] 은 단조 로 운 체감 과 동시에 우 리 는 절단 거리의 최대 치 를 요구 합 니 다.
이때 볼록 케이스 유지 하기 (경사 율 단조 로 움 감소)
코드 보기:
#include
using namespace std;
#define int long long
const int maxn=1000000+10;
int n,a,b,c,sum[maxn],f[maxn],q[maxn];
int yval(int x,int y){
    return f[y]+a*sum[y]*sum[y]-b*sum[y]-f[x]-a*sum[x]*sum[x]+b*sum[x];
}
int xval(int x,int y){
    return sum[y]-sum[x];
}
signed main(){
    cin>>n>>a>>b>>c;
    int tmp;
    for(int i=1;i<=n;i++){
        scanf("%lld",&tmp);
        sum[i]=sum[i-1]+tmp;
        f[i]=-1e12;
    }
    int l=1,r=1;
    q[l]=0;
    for(int i=1;i<=n;i++){
        while(l1])>=xval(q[l],q[l+1])*2*a*sum[i])l++;
        f[i]=f[q[l]]+a*(sum[i]-sum[q[l]])*(sum[i]-sum[q[l]])+b*(sum[i]-sum[q[l]])+c;
        while(l1],q[r])*xval(q[r],i)<=xval(q[r-1],q[r])*yval(q[r],i))r--;
        q[++r]=i;
    }
    printf("%lld
",f[n]);
    return 0;
}

 
예제 5: P4360 [CEOI 2004] 제재소 입지 선정
사이트 주소:https://www.luogu.com.cn/problem/P4360
이것 은 내 가 DP 를 기울 인 첫 번 째 로 AC 를 한 번 도 하지 않 은 이 유 는 처음으로 롱 롱 롱 을 잊 었 기 때문이다.
이 문 제 는 비교적 특수 하고 세심 한 학우 들 이 발견 한 것 이 분명 하 다.
편 의 를 위해 d 배열 의 접미사 와 sd [i] = sd [i + 1] + d [i] 를 설정 하고 k 배열 의 접두사 와 sk [i] = sk [i - 1] + k [i] (k [i] 는 제목 의 w [i]) 를 설정 합 니 다.
f [i] 를 두 번 째 제재소 에서 i 를 선택 할 때 가장 작은 값 으로 설정 합 니 다. 첫 번 째 제재소 가 j 에 있다 고 가정 하면 1 ~ j - 1 에서 j 로 운반 되 는 것 과 k [p] * (sd [p] - sd [j]), p * 8712 ° [1, n], j + 1 ~ i - 1 에서 i 로 운반 되 는 것 은 k [p] * (sd [p] - sd [i]), p * 8712 ° [j + 1, i] 입 니 다.
i + 1 ~ n 에서 세 번 째 제재소 로 운 송 된 합 은 k [p] * sd [p], p * 8712 ° [i + 1, n] 입 니 다.k [p] * sd [p] 의 합 을 sum 로 설정 합 니 다.
그럼 이 식 은 f [i] = sum - sd [j] * sk [j] - sd [i] * sd [k] + sd [i] * sk [j] 로 정 리 했 습 니 다. 놀 라 운 발견 은 전달 할 필요 가 없 었 습 니 다. 아 쉽게 도 소 용이 없 었 습 니 다.
함수 식 으로 정리: sd [j] * sk [j] = sd [i] * sk [j] + sum - f [i] - sd [i] * sk [i]
절단 거리 가 가장 크 고 경사 율 sd [i] 가 단 조 롭 게 줄 어 들 려 면 볼록 가방 을 유지 하 는 것 을 고려 하 세 요 (모 르 는 것 은 반드시 스스로 그림 을 그 려 보 세 요!!)
코드 보기:
#include
using namespace std;
#define int long long
const int maxn=50000;
int n,d[maxn],sd[maxn],sum,sk[maxn],k[maxn];
int q[maxn],f[maxn];
int yval(int a,int b){return sd[b]*sk[b]-sd[a]*sk[a];}
int xval(int a,int b){return sk[b]-sk[a];}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&k[i],&d[i]);
        sk[i]=sk[i-1]+k[i];
    }
    for(int i=n;i>=1;i--)
        sd[i]=sd[i+1]+d[i];
    for(int i=1;i<=n;i++)
        sum+=k[i]*sd[i];
    int l=1,r=1,ans=2147483647;
    for(int i=1;i<=n;i++){
        while(l1])>=xval(q[l],q[l+1])*sd[i])l++;
        f[i]=sd[i]*sk[q[l]]-sd[q[l]]*sk[q[l]]+sum-sd[i]*sk[i];
        while(l1],q[r])*xval(q[r],i)<=xval(q[r-1],q[r])*yval(q[r],i))r--;
        q[++r]=i;
        ans=min(ans,f[i]);
    }
    printf("%lld
",ans);
    return 0;
}

 
예제 6: P4072 [SDOI 2016] 여정
사이트 주소:https://www.luogu.com.cn/problem/P4072
비록 또 한 번 AC 였 지만 이 문 제 는 내 가 매우 당 황 스 럽 게 풀 었 다 고 말 할 수 밖 에 없 었 다. 그리고 십 여 분 동안 조정 했다. 비록 모두 지적 장애 가 잘못 되 었 지만.
본론 으로 돌아가다.갑자기 보 니 n 은 3000 밖 에 없 는데 경사 율 이 최적화 되 지 않 는 것 같 습 니 다.
하지만 일반 DP 는 N ^ 2 * M 이 므 로 경사 율 을 최적화 해 야 합 니 다. 하하.
구조 수열 A1 ~ Am 은 i 단의 합 을 나타 낸다.
분산 곱 하기 m ^ 2 후 이렇게 생 겼 습 니 다: m * Ai ^ 2 - (Ai) ^ 2
깜짝 발견 (Ai) ^ 2 는 정격 치 입 니 다. 그러면 우 리 는 Ai ^ 2 를 최소 화하 면 됩 니 다.
낯 이 익 냐 고?이것 은 예 일이 아 닙 니까?하지만 이 문 제 는 1 차원 이다.
상 전 방정식 을 유도 할 수 있 습 니 다: f [i] [j] = min {f [k] [j - 1] + (sum [i] - sum [k]) ^ 2}
f [...] [i] 는 f [...] [- 1] 과 만 관련 이 있 는 것 을 발견 하면 대열 에 i - 1 을 넣 고 i 의 답 을 통계 하 는 것 이 좋 겠 습 니 다.
코드 보기:
#include
using namespace std;
#define int long long
const int maxn=3000+10;
int n,m,f[maxn][maxn],sum[maxn],d[maxn],q[maxn];
int yval(int a,int b,int c){
    return f[b][c]+sum[b]*sum[b]-f[a][c]-sum[a]*sum[a];
}
int xval(int a,int b){return sum[b]-sum[a];}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%lld",&d[i]);
        sum[i]=sum[i-1]+d[i];
    }
    //memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++)
        f[i][1]=sum[i]*sum[i];
    for(int i=2;i<=m;i++){
        int l=1,r=1;
        q[l]=0;
        for(int j=1;j<=n;j++){
            while(l1],i-1)<=xval(q[l],q[l+1])*2*sum[j])l++;
            f[j][i]=f[q[l]][i-1]+(sum[j]-sum[q[l]])*(sum[j]-sum[q[l]]);
            //printf("%d %d %d %d %d
",j,i,q[l],f[q[l]][i-1],f[j][i]);
            while(l1],q[r],i-1)*xval(q[r],j)>=xval(q[r-1],q[r])*yval(q[r],j,i-1))r--;
            q[++r]=j;
            //printf("%d %d
",l,r);
        }
    }
    //for(int i=1;i<=m;i++)
    //    for(int j=1;j<=n;j++)
    //        printf("f[%d][%d]=%d
",j,i,f[j][i]);
    printf("%lld
",m*f[n][m]-sum[n]*sum[n]);    
    return 0;
}

그 디 버 깅 코드 를 보 았 습 니까?독자 각성: i 와 j 를 거꾸로 만 들 지 마!!
예제 7: P5785 [SDOI 2012] 퀘 스 트 배정
사이트 주소:https://www.luogu.com.cn/problem/P5785
이 문 제 는 그다지 같 지 않다.비용 을 통 해 미리 전달 식 길 이 를 밀 수 있 습 니 다. f [i] = min {f [j] + sumt [i] * (sumc [i] - sumc [j]) + s * (sumc [n] - sumc [j])}
함수 형식 으로 쓰기: f [j] = (s + sumt [i]) * sumc [j] + f [i] - sumt [i] * sumc [i] - s * sumc [n]
그러나 우 리 는 t 가 양수 임 을 보증 하지 않 기 때문에 sumt [i] 도 단조 성 이 없 기 때문에 2 분 동안 답 을 구 할 수 밖 에 없다 는 것 을 알 게 되 었 다.
코드 보기:
#include
using namespace std;
#define int long long
const int maxn=500000;
int n,s,t[maxn],c[maxn],f[maxn];
int st[maxn],sc[maxn],q[maxn];
int yval(int a,int b){return f[b]-f[a];}
int xval(int a,int b){return sc[b]-sc[a];}
signed main(){
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&t[i],&c[i]);
        st[i]=st[i-1]+t[i];
        sc[i]=sc[i-1]+c[i];
    }
    memset(f,0x3f,sizeof(f));
    int l=1,r=1;
    q[l]=0;f[0]=0;
    for(int i=1;i<=n;i++){
        int x=1,y=r;
        if(l!=r)
            while(x<y){
                int mid=(x+y)>>1;
                if(yval(q[mid],q[mid+1])<=(s+st[i])*xval(q[mid],q[mid+1]))x=mid+1;
                else y=mid;
            }
        f[i]=f[q[x]]+st[i]*(sc[i]-sc[q[x]])+s*(sc[n]-sc[q[x]]);
        while(l1],q[r])*xval(q[r],i)>=xval(q[r-1],q[r])*yval(q[r],i))r--;
        q[++r]=i;
    }
    printf("%lld
",f[n]);
    return 0;
}

 
response 응답 헤더 상세 정보
Red Hat 7.2 RPM 설치 Mysql 5.7.12

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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