Submission #684363

#TimeUsernameProblemLanguageResultExecution timeMemory
684363jophyyjhMountains (IOI17_mountains)C++14
100 / 100
32 ms16092 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". * * In impl2, we slightly modify the order of doing range dp: we compute the ranges * by sorting them inn decreasing order of i and increasing order of j. This * simplifies the process of finding "seeable" mountains. * * Time Complexity: O(n^3) (Full solution) * Implementation 2 (Range dp) */ #include <bits/stdc++.h> #include "mountains.h" typedef std::vector<int> vec; typedef std::complex<int> complex_t; typedef long long ll; const int INF = 2 * 1e9; inline ll cross(const complex_t& c1, const complex_t& c2) { return ll(c1.real()) * ll(c2.imag()) - ll(c1.imag()) * ll(c2.real()); } 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 i = n - 1; i >= 0; i--) { vec seen; // the mountains that can be seen by i and are on its right complex_t last_vec = {0, -INF}; int prefix_sum = 0; for (int j = i; j < n; j++) { if (cross(mounts[j] - mounts[i], last_vec) <= 0LL) { if (!seen.empty() && seen.back() + 1 <= j - 1) prefix_sum += max_d[seen.back() + 1][j - 1]; seen.push_back(j); last_vec = mounts[j] - mounts[i]; } max_d[i][j] = 1 + prefix_sum; if (seen.back() + 1 <= j) max_d[i][j] += max_d[seen.back() + 1][j]; if (i < j) max_d[i][j] = std::max(max_d[i][j], max_d[i + 1][j]); // skip i } } return max_d[0][n - 1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...