#include "mountains.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define xx first
#define yy second
#define all(v) (v).begin(), (v).end()
// * dp[l][r] : r을 반드시 포함하여 l~r에서 지을 수 있는 최대 개수
// k[] = r에서 보이는 점들의 인덱스들을 순서대로 쓴 배열.
// -> dp[l][r]은 k를 기준으로 partition을 나눠서, 각 최적을 합한 것과 같다.
// k[i] = k[]에서 l의 lower bound.
// opt(x ~ y) = 구간 [i~j]에서 max dp값.
// dp[l][r] = opt(l ~ k[i]-1) + opt(k[i]+1, k[i+1]-1) + ...+ opt(k[-2]+1, k[-1]-1) + 1
int n, dp[2020][2020], opt[2020][2020];
ll h[2020];
int get_opt(int l, int r) {
auto &ret = opt[l][r];
if(ret != -1) return ret;
ret = dp[l][r];
if(l != r)
ret = max({ret, get_opt(l+1, r), get_opt(l, r-1)});
return ret;
}
bool canSee(int l, int mid, int r) {
return (mid - l)*(h[r] - h[l]) - (r - l)*(h[mid] - h[l]) >= 0;
}
int maximum_deevs(vector<int> _y){
n = _y.size();
for(int i=1; i<=n; ++i) h[i] = _y[i-1];
for(int i=0; i<=n+1; ++i)
for(int j=0; j<=n+1; ++j)
dp[i][j] = opt[i][j] = -1;
dp[1][1] = 1;
for(int r=2; r<=n; ++r) {
vector<int> ks = {r-1};
for(int l=r-2; l>=2; --l)
if(canSee(l, ks.back(), r))
ks.push_back(l);
ks.push_back(0);
dp[r][r] = dp[r-1][r] = 1;
int opt_sum = 1;
for(int ki=1; ki<ks.size(); ++ki) {
int k2 = ks[ki-1], k1 = ks[ki];
for(int l=k1+1; l<k2; ++l)
dp[l][r] = opt_sum + get_opt(l, k2-1);
if(k1+1 <= k2-1)
opt_sum += get_opt(k1+1, k2-1);
dp[k1][r] = opt_sum;
}
}
return get_opt(1, n);
}
Compilation message
mountains.cpp: In function 'int maximum_deevs(std::vector<int>)':
mountains.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int ki=1; ki<ks.size(); ++ki) {
| ~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
316 KB |
Output is correct |
| 5 |
Correct |
0 ms |
316 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
1 ms |
468 KB |
Output is correct |
| 8 |
Correct |
0 ms |
468 KB |
Output is correct |
| 9 |
Correct |
1 ms |
468 KB |
Output is correct |
| 10 |
Correct |
1 ms |
468 KB |
Output is correct |
| 11 |
Correct |
1 ms |
468 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
444 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
316 KB |
Output is correct |
| 5 |
Correct |
0 ms |
316 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
1 ms |
468 KB |
Output is correct |
| 8 |
Correct |
0 ms |
468 KB |
Output is correct |
| 9 |
Correct |
1 ms |
468 KB |
Output is correct |
| 10 |
Correct |
1 ms |
468 KB |
Output is correct |
| 11 |
Correct |
1 ms |
468 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
444 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
316 KB |
Output is correct |
| 5 |
Correct |
0 ms |
316 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
1 ms |
468 KB |
Output is correct |
| 8 |
Correct |
0 ms |
468 KB |
Output is correct |
| 9 |
Correct |
1 ms |
468 KB |
Output is correct |
| 10 |
Correct |
1 ms |
468 KB |
Output is correct |
| 11 |
Correct |
1 ms |
468 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
444 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
316 KB |
Output is correct |
| 5 |
Correct |
0 ms |
316 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
1 ms |
468 KB |
Output is correct |
| 8 |
Correct |
0 ms |
468 KB |
Output is correct |
| 9 |
Correct |
1 ms |
468 KB |
Output is correct |
| 10 |
Correct |
1 ms |
468 KB |
Output is correct |
| 11 |
Correct |
1 ms |
468 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
444 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
