AOJ 2063 : TV Watching - 土下座しながら探索中

問題リンク : TV Watching | Aizu Online Judge

問題概要 :
N本のテレビ番組の情報が与えられる
同じ時刻に複数の番組を同時に見ることは不可能なので、自分はそのテレビ番組をリアルタイムで見るか録画して後で見るかを選べる
リアルタイムで見た時の満足度と録画して見た時の満足度が各番組毎に与えられるので満足度を最大化せよ
番組を見終わってすぐに次の番組を見ることができる ( 例えば, 12:00に見終わってすぐに12:00から始まる番組を見れる )
同じ時刻にリアルタイムで見れる番組は１つまで
同じ時刻に録画できる番組は１つまで

解法：
重み付き区間スケジューリングみたいな問題
テレビの放送時間をセグメントとして終わる時刻が早い順にソートする ( それとその前に、0:00開始0:00終了で生で見たら0point,録画してみたら0pointの番組をスタートとして追加する )

dp[i][j] := リアルタイムでは番組iまでみて、録画ではjまでみた時の満足度の最大値

for i 0..N // リアルタイムでどの番組まで見たか
  for j 0..N // 録画でどの番組まで見たか

というループで見ていく

普通の重み付き区間スケジューリングを応用するとできるので、
アルゴリズムデザイン(黒くて鷹の絵が書いてある本、英語版は~~カマキリの卵だったような気がする~~ 良く分からない鳥だった)のP230,231を読んでみるとこっちもなんとなく分かると思う

サンプルケース :
upper_boundとlower_boundを間違えてWA叩き出した時につくったケースを載せておく

Sample Input :

3
a 0:00 1:00 10 5
b 0:00 1:00 10 5
c 1:00 2:00 10 5
5
c 00:00 07:00 100 1
a 01:00 03:00 1 100
i 02:00 05:00 1 100
b 04:00 05:00 1 100
e 05:00 06:00 1 100
7
a 0:00 12:00 10 4
b 2:00 11:00 1 10
c 1:00 1:30 11 12
d 13:00 14:12 14 12
e 23:00 23:59 20 11
f 0:00 23:59 31 22
g 17:00 18:00 20 14
13
a 0:00 1:00 60 100
b 0:00 1:00 100 60
c 0:00 1:30 120 130
d 2:00 3:00 51 11
e 3:00 4:00 56 56
f 4:00 5:00 11 12
g 1:00 5:00 100 12
h 4:15 5:15 120 130
i 6:00 9:15 12 41
j 3:00 7:00 200 12
k 3:15 5:16 199 150
l 6:15 7:44 24 155
m 7:12 8:30 125 122
0

Sample Output :

コード :

#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;

struct Data {
  int start,end,onAir,recorded;
  bool operator < ( const Data &data ) const {
    if( end != data.end ) return end < data.end;
    if( start != data.start ) return start < data.start;
    return ( onAir != data.onAir ) ? onAir < data.onAir : recorded < data.recorded;
  }
};

const int MAX_N = 1100;
int N,dp[2000][2000],h,m;
vector<int> buf;

int toTime(string s){
  rep(i,(int)s.size()) if( s[i] == ':' ) s[i] = ' ';
  stringstream ss(s);
  ss >> h >> m;
  return h * 60 + m;
}

int main(){
  while( cin >> N, N ){
    vector<Data> vec(N);
    rep(i,N) {
      string a,b,c;
      cin >> a >> b >> c >> vec[i].onAir >> vec[i].recorded;
      vec[i].start = toTime(b), vec[i].end = toTime(c);
    }
    vec.push_back((Data){0,0,0,0});
    rep(i,N+2) rep(j,N+2) dp[i][j] = 0; 
    sort(vec.begin(),vec.end());
    buf.clear();
    rep(i,vec.size()) buf.push_back(vec[i].end);
    rep(i,vec.size()){
      rep(j,vec.size()){
        if( i == j ) dp[i][j] = max((i?dp[i-1][j]:0),(j?dp[i][j-1]:0));
        else if( i < j ) {
          int prev = upper_bound(buf.begin(),buf.begin()+j,vec[j].start) - buf.begin() - 1;
          dp[i][j] = max(dp[i][j-1],((prev!=-1)?dp[i][prev]:0)+vec[j].recorded);
        } else {
          int prev = upper_bound(buf.begin(),buf.begin()+i,vec[i].start) - buf.begin() - 1;
          dp[i][j] = max(dp[i-1][j],((prev!=-1)?dp[prev][j]:0)+vec[i].onAir);
        }
      }
    }
    printf("%d\n",dp[(int)vec.size()-1][(int)vec.size()-1]);
  }
  return 0;
}