POJ 1180 Batch Scheduling
2172 단어 poj기울 기 최적화 DP
제목: N 개의 jobs 를 드 리 겠 습 니 다. 한 대 이상 의 기 계 를 사용 하 라 고 합 니 다. 차례 완성 한 후에 모든 기계 가 작 동 하기 전에 S 의 시간 이 필요 합 니 다.
만약 기계 한 대가 3 개의 jobs 를 완성 한다 면, 이 3 개의 jobs 가 완성 하 는 시간 은 모두 tt =(시작 시간 + S + t [a] + t [b] + t [c]);
그래서 대 가 는 tt * f [a] + tt * f [b] + tt * f [c] 입 니 다.
모든 jobs 를 완성 하 는 최소한 의 대가
이 문제 의 어 려 운 점 은 가장 좋 은 방법 으로 몇 대의 기 계 를 사용 할 지 모 르 는 것 이다. 앞 에 몇 대의 기 계 를 사용 하면 뒤의 상태 에 영향 을 줄 수 있다 는 것 이다.
그래서 우 리 는 거꾸로 밀어 볼 수 있다.
dp [i] i - n 의 jobs 를 완성 하 는 데 필요 한 대 가 를 나타 낸다.
그리고 있 을 거 예요.
st [i] 는 t [i] + t [i + 1] +... + t [n];
sf [i] 는 f [i] + f [i + 1] +... + f [n];
dp[i] = dp[k] + (s + st[i] - st[k]) * (sf[i] - sf[k]) + (s + st[i] - st[k]) * sf[k]; i
다음은 일반적인 경사 율 최적화 DP 입 니 다.
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int INF = 1 << 30;
const int N = 10005;
int st[N], sf[N], q[N], t[N], f[N];
int dp[N];
int n,s;
int getdp(int i, int k){
return dp[k] + (s + st[i] - st[k]) * sf[i];
}
int getup(int j, int k){
return dp[j] - dp[k];
}
int getdown(int j, int k){
return st[j] - st[k];
}
int main(){
int head, tail;
while(~scanf("%d%d",&n,&s)){
memset(dp,0,sizeof(dp));
for(int i = 1; i <= n; i++){
scanf("%d%d", t+i, f+i);
}
st[n+1] = sf[n+1] = 0;
for(int i = n; i > 0; i--){
st[i] = st[i+1] + t[i];
sf[i] = sf[i+1] + f[i];
}
head = tail = 0;
q[tail++] = n+1;
for(int i = n; i > 0; i--){
while(head < tail-1 && getup(q[head+1], q[head]) <= sf[i] * getdown(q[head+1], q[head]))
head++;
dp[i] = getdp(i,q[head]);
while(head < tail-1 && getup(q[tail-2], q[tail-1]) * getdown(q[tail-1], i) >= getup(q[tail-1], i) * getdown(q[tail-2], q[tail-1]))
tail--;
q[tail++] = i;
}
printf("%d
",dp[1]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3071: Football(확률 DP)Consider a single-elimination football tournament involving 2n teams, denoted 1, 2, …, 2n. After n rounds, only one team...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
