結果
問題 | No.484 収穫 |
ユーザー |
![]() |
提出日時 | 2018-11-06 17:03:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 42 ms / 3,000 ms |
コード長 | 864 bytes |
コンパイル時間 | 1,846 ms |
コンパイル使用メモリ | 196,784 KB |
最終ジャッジ日時 | 2025-01-06 15:40:20 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include<bits/stdc++.h> using namespace std; using Int = long long; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} //INSERT ABOVE HERE const Int MAX = 2020; const Int INF = 1e15; Int dp[MAX][MAX]; signed main(){ Int n; cin>>n; vector<Int> a(n); for(Int i=0;i<n;i++) cin>>a[i]; for(Int i=0;i<MAX;i++) for(Int j=0;j<MAX;j++) dp[i][j]=INF; dp[0][n-1]=0; dp[n-1][0]=0; for(Int w=n;w>1;w--){ for(Int i=0;i+w-1<n;i++){ Int j=i+w-1; chmin(dp[i][j],dp[j][i]+(j-i-1)); chmin(dp[j][i],dp[i][j]+(j-i-1)); chmin(dp[i+1][j],max(dp[i][j],a[i])+1); chmin(dp[j-1][i],max(dp[j][i],a[j])+1); } } Int ans=INF; for(Int i=0;i<n;i++) chmin(ans,max(dp[i][i],a[i])); cout<<ans<<endl; return 0; }