SRM 320 Div1 Medium ContestSchedule

問題

プログラミングコンテストがいくつか開かれ、それらの開始時間、終了時間、勝率が空白で区切られた１つの文字列"s t p"の形式で与えられる。あるコンテストに出場している間は他のコンテストには出場できない。最適な出場の仕方をした時に、勝てるコンテストの期待値を計算せよ。コンテスト終了した時刻と他のコンテストの開始時刻が同じ場合はそれに出場できるものとする。

やりかた

重み付き区間スケジューリング問題なのでDPでいける。
まずはコンテストの開始時刻でソートして上で次のDP。
dp[i][j]:=（i番目のコンテストまで見ていて、前回出場したコンテストがjのときの勝利回数の最大期待値）
i番目のコンテストに出場できるにはi番目のコンテストの開始時刻がj番目のコンテストの終了時刻以降である必要がある。

以下ソース。

class ContestSchedule {
public:
  ll sti(string s){
    stringstream ss(s);
    ll ret; ss >> ret; return ret;
  }
  double expectedWinnings(vector <string> contests){
    int N = contests.size();
    vector<pair<pair<ll, ll>, double>> t;
    for(int i = 0; i < N; i++){
      string tmp = contests[i];
      stringstream ss(tmp); 
      string a, b, c; ss >> a >> b >> c;
      t.push_back(make_pair(make_pair(sti(a), sti(b)), sti(c) * 0.01));
    }
    sort(ALL(t));
    vector<vector<double>> dp(N + 1, vector<double>(N + 1, 0.0));
    for(int i = 0; i < N; i++) dp[i + 1][i] = t[i].second;
    for(int i = 0; i < N; i++){
      for(int j = 0; j < i; j++){
        //i番目のコンテストに出場できるにはi番目のコンテストの開始時刻がj番目のコンテストの終了時刻以降である必要がある
	if(t[i].first.first >= t[j].first.second)
	  dp[i + 1][i] = max(dp[i + 1][i], dp[i][j] + t[i].second);
	dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
      }
    }
    double ans = 0.0;
    for(int i = 0; i <= N; i++) ans = max(ans, dp[N][i]);
    return ans;
  }
};
  

DPはまだ簡略化できるはず。もっとDPをやる必要がありそう。