COLOCON -Colopl programming contest 2018 D - すぬけそだて――トレーニング――
問題ページ D - すぬけそだて――トレーニング――
このブログは解説ではなくクソポエムです
感想
解説を実装しただけ
実装に無駄に時間をかけてしまったので反省
lower_boundとかupper_boundでいまだに混乱するのをやめたい
monge性とかスライド最小値、セグ木でDPの遷移を高速化するやつはまだいらないテクかなーと思って放置していたけど強い人がアルゴリズムで殴るのに使っていたしそろそろ覚えたい。勉強して通したら追記する。
#define __USE_MINGW_ANSI_STDIO 0 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VL; typedef vector<VL> VVL; typedef pair<int, int> PII; #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 IN(a, b, x) (a<=x&&x<b) #define MP make_pair #define PB push_back #ifdef int const ll INF = (1LL<<60); #else const int INF = (1LL<<30); #endif const double PI = 3.14159265359; const double EPS = 1e-12; 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<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // dp[i][j] = (T[i]が最後に起動した時刻でそれまでにj回起動している) // t[i]から遷移する先は2パターンしかない int dp[5010][5010], t[5010], nxt[5010]; signed main(void) { int n, x; cin >> n >> x; REP(i, n) cin >> t[i]; REP(i, n) { // t[i] + X >= t[j] となる最大のjを求めておく int lb = 0, ub = n; while(ub - lb > 1) { int mid = (ub+lb)/2; if(t[i] + x >= t[mid]) lb = mid; else ub = mid; } nxt[i] = lb; } dp[0][0] = x; REP(i, n) REP(j, n) { // dp[i][j] からは dp[nxt[i]][j+1] と dp[nxt[i]+1][j+1] に遷移 chmax(dp[nxt[i]][j+1], dp[i][j] + min(t[nxt[i]] - t[i], x)); chmax(dp[nxt[i]+1][j+1], dp[i][j] + min(t[nxt[i]+1] - t[i], x)); } REP(i, n) { int ret = 0; REP(j, n) { chmax(ret, dp[j][i]); } cout << ret << endl; } return 0; }