[CEOI2004] 톱날 공장 입지 [사율 최적화]

4208 단어 문제풀이
이 문제는 간단한 경사율 최적화 DP의 입문 문제입니다.
우리는 먼저 소박한 DP 방정식을 썼다.
dp[i]=totsum−dis[j]∗sum[j]−dis[i]∗(sum[i]−sum[j])(j그 중에서 dp[i] dp[i]는 현재 두 번째 공장에서 i번 나무의 위치를 정할 때 가장 적은 비용을 나타내고, totsum t o t s um는 모든 나무가 처음에 모두 운송된 산기슭의 비용을 나타내며, dis[i] d i s [i]는 거리의 접미사와 (우리는 위에서 아래로 운반하기 때문에),sum[i] s um [i]는 나무의 무게를 나타내는 접미사와 접미사를 나타낸다.그러면 i, ji, j에서 공장을 수리한 후 총 비용은 totsum t o t s um에서 j 공장에서 산기슭까지 운반하는 추가 비용을 뺀 dis[j] ∗sum[j] di s[j] 𕓭s um[j], ii공장에서 산기슭으로 운반하는 추가 비용을 뺀 dis[i] 𕓭(sum[i] --sum[j] di s[i] 𕓭(um i)
형상적으로 말하면 당신이 먼저 jj 앞에 있는 목재를 jj공장으로 운반한 다음에 이 목재를 산기슭으로 운반하는 비용을 줄이고 i, ji, j 사이의 목재를 i공장으로 운반한 다음에 그것들이 산기슭까지 운반하는 비용을 줄인다.
그리고 우리는 DP 방정식을 변형시켜 j, k(jtotsum -dis [k] -dis [i] 𕓬(sum[i] -sum [k]) t t s u m -d i s [j]\87us [j] i] i(i] i) t t t t s u m [k] t t s [h] t s [j] [j] [j] i] i] i] i, i, i, i, i, i, i, i, i, i, i, i, i, i, i, i, i, i, i, i, i, i, i, i, i, i, i, i, i, i, i, i, i, i, it s u m: d i s [k]::d i s [i]: (s u m [i]: s u m [k])
정리 후 알 수 있듯이 dis[j] dis[j] dis[k] sum[j] - sum[k] dis[k]> dis[i] d i s [j] dis[j] dis[um [j] dis[k] dis[k] dis] u m [k] s u m [j] - dis[k]
그리고 경사율 dis[i] d i s[i]는 ii가 증가함에 따라 작아지기 때문에 우리는 경사율에 따라 상철각을 유지한다. 단조로운 것이기 때문에 하나의 대열을 사용하면 된다.
추악한 코드가 신선하게 나왔습니다~~~
코드 중sum은totsum,s[i]는sum[i],d[i]는dis[i]입니다.

#include
#include
#include
#define db double
using namespace std;
const int M=3e4+1;
int n;
int q[M],fi,la,ans=2e9+1;
int sum,s[M],d[M],w[M];
db calc(int j,int k){return 1.0*(d[j]*s[j]-d[k]*s[k])/(s[j]-s[k]);}
int count(int i,int j){return sum-d[j]*s[j]-d[i]*(s[i]-s[j]);}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){scanf("%d%d",&w[i],&d[i]);}
    for(int i=n;i>=1;i--) d[i]+=d[i+1];
    for(int i=1;i<=n;i++) s[i]=s[i-1]+w[i],sum+=d[i]*w[i];
    for(int i=1;i<=n;i++){
        while(fi1])>d[i]) ++fi;
        ans=min(ans,count(i,q[fi]));
        while(fi1],q[la])printf("%d
",ans);
    return 0;
}
[초보자] 백그라운드:url();이미지를 표시하지 않는 문제 해결
루비 초보자 과제 return 역할 영역 방법

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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