ferinの競プロ帳

競プロについてのメモ

AOJ1246 Concert Hall Scheduling

問題ページ
Concert Hall Scheduling | Aizu Online Judge

考えたこと

  • 区間が飛んでくるのでとりあえず終端でソートする
  • 区間が3つ以上かぶるような日があるとだめ
  • 今までに選んだ区間ですでに2つかぶっているような日が存在
  • その日よりも始点が前の区間を使うのは不可能
  • 終点でソートしてるので始点が前にあると確実に内包しているといえる
  • かぶっている日のうち最も遅い日付が意味がある
  • 終点ソートしてるのでもっと前でかぶっていたら最も遅い日でもかぶっているので
  • すでに1つ、2つかぶっているような日付を持っておきたい
  • dp[i番目][2つかぶっている最も遅い日][1つ被っている最も遅い日] = (最大の収入)
  • 日付の最大をLとすると計算量がO(NL^2)で間に合いそう
  • dpテーブルを全部持つとMLEしそうなので2つだけもつ空間削減テクをする
  • 通る

とりあえず終点ソートするの本当に強い
終点ソートしてあると見るべきものが減るパターンが多い

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int dp[2][405][405];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(true) {
    int n;
    cin >> n;
    if(!n) break;
    VVI v;
    REP(i, n) {
      int l, r, w;
      cin >> l >> r >> w;
      v.PB({r, l, w});
    }

    sort(ALL(v));

    memset(dp, -1, sizeof(dp));
    int cur = 0, nxt = 1;
    dp[cur][0][0] = 0;
    REP(i, n) {
      REP(j, 366) REP(k, 366) {
        if(dp[cur][j][k] == -1) continue;
        int l = v[i][1], r = v[i][0], w = v[i][2];
        // iを使う
        if(l > j) {
          int nj = l <= k ? k : j;
          chmax(dp[nxt][nj][r], dp[cur][j][k] + w);
        }
        // iを使わない
        chmax(dp[nxt][j][k], dp[cur][j][k]);
      }
      // curとnxtをうまくやるやつ
      swap(cur, nxt);
      REP(j, 366) REP(k, 366) dp[nxt][j][k] = -1;
    }

    int ans = 0;
    REP(i, 366) REP(k, 366) chmax(ans, dp[cur][i][k]);
    cout << ans << endl;
  }

  return 0;
}