제출 #684360

#제출 시각아이디문제언어결과실행 시간메모리
684360jophyyjhMountains (IOI17_mountains)C++14
컴파일 에러
0 ms0 KiB
/** * It took me long before I can even find 1 dp solution. At some point, I started to * consider the heights in decreasing order. Let the height of the highest * mountain(s) be h, and let m_1, m_2, ..., m_k be the mountain(s) attaining h from * left to right. Clearly, {m_1, ..., m_k} can see each other, so at most one of them * can be chosen. Now, the remaining mountains are partitioned into (k+1) contigous * segments, and we know that mountains from different segments can't see each other * (cuz they're separated by a mountain with height h)! In other words, the segments * are "somewhat independent", prompting us to consider range dp. * * Let's do some rigorous reasoning. Suppose that we're finding the max num of deevs * that can be imprisoned with mountains [i,j]. If mountain i is not chosen, the ans * is the same as [i+1,j]'s. If mountain i (s) is chosen, we notice sth~ * Let m_1, m_2, ..., m_l be the mountains (in [i+1,j] from left to right) that can * be seen by mount i. Here're some observations: * (1) "Seeing" is a mutual relationship, i.e. a can see b iff b can see a; * (2) Lines sm_1, sm_2, sm_3, ..., sm_l have non-decreasing slope; * (3) None of m_1, m_2, ..., m_l can be chosen; * (4) Similarly, after neglecting m_1, ..., m_l, mountains [i+1,j] are partitioned * into several contigous segments. We claim that each segment is independent * of each other, which means that each segment adds a dp ans of a smaller range * to the dp val of [i,j]. This is true because of [Lemma]. * [Lemma] If mountain a can see mountain b and c, and a cannot see any mountains * between b, c (a is to the left of b and b is to the left of c), then a * cannot see any mountains between b and c. * Note that the statement implys that from mountain a, b and c are "adjacent seeable * mountains". * * Time Complexity: O(n^3) (Solves [S1-3]) * Implementation 1 (Range dp) */ #include <bits/stdc++.h> #include "mountains.h" typedef std::vector<int> vec; typedef std::complex<int> complex_t; const int INF = 2 * 1e9; inline int cross(const complex_t& c1, const complex_t& c2) { return (std::conj(c1) * c2).imag(); } int maximum_deevs(vec values) { int n = values.size(); std::vector<complex_t> mounts(n); for (int k = 0; k < n; k++) mounts[k] = complex_t{k, values[k]}; std::vector<vec> max_d(n, vec(n)); for (int diff = 0; diff < n; diff++) { for (int i = 0, j = diff; j < n; i++, j++) { vec seen; // the mountains that can be seen by i and are on its right complex_t last_vec = {i, -INF}; for (int k = i + 1; k <= j; k++) { if (cross(mounts[k] - mounts[j], last_vec) >= 0) { seen.push_back(k); last_vec = mounts[k] - mounts[j]; } } int m = seen.size(); max_d[i][j] = 1; for (int k = 0; k < m - 1; k++) { if (seen[k] + 1 <= seen[k + 1] - 1) max_d[i][j] += max_d[seen[k] + 1][seen[k + 1] - 1]; } if (m > 0 && seen[m - 1] + 1 <= j) max_d[i][j] += max_d[seen[m - 1] + 1][j]; if (i < jpui) max_d[i][j] = std::max(max_d[i][j], max_d[i + 1][j]); // skip i } } return max_d[0][n - 1]; }

컴파일 시 표준 에러 (stderr) 메시지

mountains.cpp: In function 'int maximum_deevs(vec)':
mountains.cpp:71:21: error: 'jpui' was not declared in this scope
   71 |             if (i < jpui)
      |                     ^~~~