UVa 607 : Scheduling Lectures

UVa演習 2014/6/17 (火) 問１

問題リンク : Scheduling Lectures

問題概要：
n個のジョブがあり、それぞれ処理にt[i]秒だけ時間がかかる
ジョブは0から順番に番号付けられていて、0から順に処理されていかなければならない
１つのプロセッサーで処理できるジョブの数は、割り当てたジョブにかかる時間の合計がL以下であればいくつでも割り当てれる
全てのジョブを終わらせるために必要なプロセッサーの数を最小化せよ
また、プロセッサーの数が同一だった場合はプロセッサーの余った時間からコストが発生するのでその合計を最小とするようにせよ

解法 :
DPする
dp[i番目のジョブまでやった][時間%(L+1)] = (必要なプロセッサーの数の最小、コストの最小)

Outputの出力の間には空行を出力することを忘れずに
これを忘れるとPresentation ErrorではなくWrong Answerとなる

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef pair<int,int> ii;
const int IINF = INT_MAX;

int buf[1010];
ii dp[1010][510];

ii compute(int n,int L,int C){
  rep(i,n+1) rep(j,L+1) dp[i][j] = ii(IINF,IINF); // ii(lec,DI)
  dp[0][0] = ii(1,0);

  rep(i,n) rep(j,L+1) if( dp[i][j] != ii(IINF,IINF) ){

    int coef = 0;
    int t = L - j;
    if( 1 <= t && t <= 10 ) coef = -C;
    else if( t )            coef = (t-10) * (t-10);
    dp[i+1][buf[i]] = min(dp[i+1][buf[i]],ii(dp[i][j].first+1,dp[i][j].second+coef));
    
    if( j + buf[i] <= L ) dp[i+1][j+buf[i]] = min(dp[i+1][j+buf[i]],dp[i][j]); 
  }
  
  ii ret = ii(IINF,IINF);
  rep(i,L+1) if( dp[n][i] != ii(IINF,IINF) ) {
    int coef = 0;
    int t = L - i;
    if( 1 <= t && t <= 10 ) coef = -C;
    else if( t )            coef = (t-10) * (t-10);
    if( i == 0 ) coef = 0;
    dp[n][i].second += coef;
    ret = min(ret,dp[n][i]);
  }
  return ret;
}

int main(){
  int n,L,C,CNT=1;
  while( cin >> n, n ){
    cin >> L >> C;
    rep(i,n) cin >> buf[i];

    int minlen;
    if( CNT != 1 ) puts("");
    printf("Case %d:\n",CNT++);
    ii res = compute(n,L,C);
    printf("Minimum number of lectures: %d\n",res.first);
    printf("Total dissatisfaction index: %d\n",res.second);
  }
  return 0;
}