結果
問題 |
No.1606 Stuffed Animals Keeper
|
ユーザー |
![]() |
提出日時 | 2023-11-18 04:38:22 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,396 ms / 3,000 ms |
コード長 | 1,603 bytes |
コンパイル時間 | 1,664 ms |
コンパイル使用メモリ | 112,316 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-26 05:39:26 |
合計ジャッジ時間 | 55,082 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 48 |
ソースコード
#include<algorithm> #include<iostream> #include<vector> #include<map> #include<cassert> #include<set> using namespace std; using ll = long long; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin>>n; vector<int> a(n); for(int i = 0;i<n;i++) cin>>a[i]; vector<vector<int>> dp(n+1,vector<int>(3,1e9)); dp[0][2] = 0; for(int i = 0;i<n;i++){ vector<vector<int>> ndp(n+1,vector<int>(3,1e9)); if(a[i]==2){ for(int j = 0;j<=n;j++){ ndp[j][2] = min(ndp[j][2],dp[j][0]); ndp[j][2] = min(ndp[j][2],dp[j][1]); ndp[j][2] = min(ndp[j][2],dp[j][2]); } swap(ndp,dp); continue; } for(int j = 0;j<=n;j++){ if(a[i]==0){ if(j+1<=n) ndp[j+1][0] = min(ndp[j+1][0],dp[j][0]); if(j+1<=n) ndp[j+1][0] = min(ndp[j+1][0],dp[j][2]); ndp[j][1] = min(ndp[j][1],dp[j][1]+1); ndp[j][1] = min(ndp[j][1],dp[j][2]+1); }else{ if(j+1<=n) ndp[j+1][0] = min(ndp[j+1][0],dp[j][0]+1); if(j+1<=n) ndp[j+1][0] = min(ndp[j+1][0],dp[j][2]+1); ndp[j][1] = min(ndp[j][1],dp[j][1]); ndp[j][1] = min(ndp[j][1],dp[j][2]); } } swap(ndp,dp); } int ans = 1e9; int cnt = 0; for(int i = 0;i<n;i++) if(a[i]==0) cnt++; ans = dp[cnt][0]; ans = min(ans,dp[cnt][1]); ans = min(ans,dp[cnt][2]); if(ans==1e9) ans = -1; else ans = ans / 2; cout<<ans<<endl; }