| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 320052 | vipghn2003 | Mountains (IOI17_mountains) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N=2005;
int n,dp[N][N];
pii point[N];
bool check(int l,int best,int r)
{
long long val=1ll*(point[best].fi-point[l].fi)*(point[r].se-point[l].se)-1ll*(point[best].se-point[l].se)*(point[r].fi-point[l].fi);
return (val>=0);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n;
for(int i=0;i<n;i++)
{
cin>>point[i].se;
point[i].fi=i;
}
for(int r=1;r<=n;r++)
{
dp[r][r]=1;
dp[r-1][r]=1;
int best=r-1,cur=0;
for(int l=r-2;l>=0;l--)
{
if(check(l-1,best-1,r-1))
{
cur+=dp[l+1][best-1];
best=l;
}
dp[l][r]=max(dp[l][r-1],cur+1+dp[l][best-1]);
}
}
cout<<dp[1][n];
}