首页 > 代码库 > poj 1180 Batch Scheduling（DP-单调性优化）

poj 1180 Batch Scheduling（DP-单调性优化）

2024-07-09 08:25:01   219人阅读

Batch Scheduling
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 3145 Accepted: 1442

Description

There is a sequence of N jobs to be processed on one machine. The jobs are numbered from 1 to N, so that the sequence is 1,2,..., N. The sequence of jobs must be partitioned into one or more batches, where each batch consists of consecutive jobs in the sequence. The processing starts at time 0. The batches are handled one by one starting from the first batch as follows. If a batch b contains jobs with smaller numbers than batch c, then batch b is handled before batch c. The jobs in a batch are processed successively on the machine. Immediately after all the jobs in a batch are processed, the machine outputs the results of all the jobs in that batch. The output time of a job j is the time when the batch containing j finishes. 

A setup time S is needed to set up the machine for each batch. For each job i, we know its cost factor Fi and the time Ti required to process it. If a batch contains the jobs x, x+1,... , x+k, and starts at time t, then the output time of every job in that batch is t + S + (Tx + Tx+1 + ... + Tx+k). Note that the machine outputs the results of all jobs in a batch at the same time. If the output time of job i is Oi, its cost is Oi * Fi. For example, assume that there are 5 jobs, the setup time S = 1, (T1, T2, T3, T4, T5) = (1, 3, 4, 2, 1), and (F1, F2, F3, F4, F5) = (3, 2, 3, 3, 4). If the jobs are partitioned into three batches {1, 2}, {3}, {4, 5}, then the output times (O1, O2, O3, O4, O5) = (5, 5, 10, 14, 14) and the costs of the jobs are (15, 10, 30, 42, 56), respectively. The total cost for a partitioning is the sum of the costs of all jobs. The total cost for the example partitioning above is 153. 

You are to write a program which, given the batch setup time and a sequence of jobs with their processing times and cost factors, computes the minimum possible total cost. 

Input

Your program reads from standard input. The first line contains the number of jobs N, 1 <= N <= 10000. The second line contains the batch setup time S which is an integer, 0 <= S <= 50. The following N lines contain information about the jobs 1, 2,..., N in that order as follows. First on each of these lines is an integer Ti, 1 <= Ti <= 100, the processing time of the job. Following that, there is an integer Fi, 1 <= Fi <= 100, the cost factor of the job.

Output

Your program writes to standard output. The output contains one line, which contains one integer: the minimum possible total cost.

Sample Input

5
1
1 3
3 2
4 3
2 3
1 4

Sample Output

153
题意：N个任务（按顺序编号1——N），1台机器。告诉你完成每个任务需要的时间Ti和完成每个任务的花费有关因素Fi。要你把这些任务分n(任意)批完成（同一批必须是相邻的），同一批任务完成的时间点相同。开始每一批任务之前需要启动机器，时间为S。每个任务的花费是完成的时间点t*Fi。
例如：
ID   1   2   3   4
T = {1 , 2 , 3 , 4};
F = {5 , 6 , 7 , 8};
S = 1;
把任务分成{1,2}、{3}、{4}；
第一批完成花费：(S+T1+T2)*(F1+F2) = (1+1+2)*(5+6) = 44;
第二批完成花费：(S+T1+T2+S+T3)*F3 = (1+1+2+1+3)*7 = 56;
第三批完成花费：(S+T1+T2+S+T3+S+T4)*F4 = (1+1+2+1+3+1+4)*8 = 104;
总花费：44+56+104 = 204.
求最少花费。
思路：
DP[i] 表示第i-n个任务的最少花费。
DP[i] = min(DP[j]+(S+sumT[i]-sumT[j])*sumF[i]),
其中sumT[i]=sum{Ti+...Tn}，sumF=sum{Fi+...Fn},j>i.
那么，我们正常的做法是枚举i(从n->1)，然后枚举j，求出最小的，即：
for(int i = n; i >= 1; i--){
    for(int j = i+1; j <= n+1; j++){
        dp[i] = min(dp[i] , dp[j]+(S+sumT[i]-sumT[j])*sumF[i]);
    }
}
dp[n+1]=0.
这样效率是n*n，超时！
假设现在我要找i+1~n中的min(dp[j]+(S+sumT[i]-sumT[j])*sumF[i])),
若dp[j]+(S+sumT[i]-sumT[j])*sumF[i]) >= dp[k]+(S+sumT[i]-sumT[k])*sumF[i])则我们取k.
=>dp[j]-dp[k] >= (sumT[j]-sumT[k])*sumF[i];
=>分类讨论：
当 j>k:  (dp[j]-dp[k])/(sumT[j]-sumT[k]) <= sumF[i];(1)
当 j<k:  (dp[j]-dp[k])/(sumT[j]-sumT[k]) >= sumF[i];(2)
因此,如果我们找到的最小值是取k，则j>k的必定满足(1)，j<k的必定满足(2)。
那么，当我们要找i~n时，当j>k必定满足(dp[j]-dp[k])/(sumT[j]-sumT[k]) <= sumF[i] <= sumF[i-1]
所以，我们就不用再去遍历j>k的那些数了！
int k = n+1;
for(int i = n; i >= 1; i--){
    int t = k;
    for(int j = i+1; j < k; j++){
        if(dp[j]+(S+sumT[i]-sumT[j])*sumF[i]) < dp[t]+(S+sumT[i]-sumT[t])*sumF[i])){
            t = j;
        }
    }
    k = t;
    dp[i] = dp[t]+(S+sumT[i]-sumT[t])*sumF[i]);
} 
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

const int maxn = 10010;
int sumT[maxn] , sumF[maxn] , dp[maxn] , S , n;

void initial(){
    for(int i = 0; i < maxn; i++){
        sumT[i] = 0;
        sumF[i] = 0;
        dp[i] = 0;
    }
}

void readcase(){
    scanf("%d" , &S);
    for(int i = 0; i < n; i++){
        scanf("%d%d" , &sumT[i] , &sumF[i]);
    }
}

void computing(){
    for(int i = n-1; i >= 0; i--){
        sumT[i] += sumT[i+1];
        sumF[i] += sumF[i+1];
    }
    int k = n;
    for(int i = n-1; i >= 0; i--){
        int t = k;
        for(int j = i+1; j < k; j++){
            if(dp[j]+(S+sumT[i]-sumT[j])*sumF[i] < dp[t]+(S+sumT[i]-sumT[t])*sumF[i]){
                t = j;
            }
        }
        k = t;
        dp[i] = dp[t]+(S+sumT[i]-sumT[t])*sumF[i];
    }
    printf("%d\n" , dp[0]);
}

int main(){
    while(scanf("%d" , &n) != EOF){
        initial();
        readcase();
        computing();
    }
    return 0;
}
































        

            
                
                  
                
                

                    联系

                    我们