#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define wall cerr<<"-------------------------------------"<<endl
typedef long long ll;
const ll INF = 1e18;
const ll maxn = 1e5 + 10;
ll n , a[maxn] , mn[maxn];
vector<pll> ve[32];
vector<pll> seg[maxn];
ll dp[32][maxn][32][2];
int main()
{
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
cin>>n;
for(int i=1; i<=n; i++){
cin>>a[i];
}
for(int l=1; l<=n; l++){
for(int j=0; j<30; j++){
int len = 1ll<<j , r=l+len-1;
if(r>n)break;
ve[j].push_back({l,r});
}
}
for(int i=0; i<30; i++){
for(auto e : ve[i]){
int l=e.F , r=e.S , mid=l+(1ll<<(i-1));
for(int k=0; k<30; k++){
dp[i][l][k][0] = INF;
dp[i][l][k][1] = INF;
}
}
}
for(auto e : ve[0]){
int pos = e.F;
dp[0][pos][a[pos]][0] = 0;
if(a[pos]<1)continue;
dp[0][pos][a[pos]-1][1] = 1;
}
/****/
for(int i=1; i<30; i++){
for(auto e : ve[i]){
int l=e.F , mid=l+(1<<(i-1));
for(int k=0; k<30; k++){
dp[i][l][k][0] = min(dp[i][l][k][0] , dp[i-1][l][k][1]+dp[i-1][mid][k][0]);
dp[i][l][k][0] = min(dp[i][l][k][0] , dp[i-1][l][k][1]+dp[i-1][mid][k][1]);
dp[i][l][k][0] = min(dp[i][l][k][0] , dp[i-1][l][k][0]+dp[i-1][mid][k][0]);
dp[i][l][k][0] = min(dp[i][l][k][0] , dp[i-1][l][k][0]+dp[i-1][mid][k][1]);
dp[i][l][k][1] = min(dp[i][l][k][1] , dp[i-1][l][k+1][1]+dp[i-1][mid][k+1][0]+1);
dp[i][l][k][1] = min(dp[i][l][k][1] , dp[i-1][l][k+1][1]+dp[i-1][mid][k+1][1]+1);
dp[i][l][k][1] = min(dp[i][l][k][1] , dp[i-1][l][k+1][0]+dp[i-1][mid][k+1][0]+1);
dp[i][l][k][1] = min(dp[i][l][k][1] , dp[i-1][l][k+1][0]+dp[i-1][mid][k+1][1]+1);
}
}
}
/***/
/*for(int i=0; i<3; i++){
for(auto e : ve[i]){
int l=e.F , mid=l+(1<<(i-1));
for(int k=0; k<4; k++){
cout<<e.F<<"-"<<e.S<<", +"<<k<<" , not : "<<dp[i][l][k][0]<<endl;
cout<<e.F<<"-"<<e.S<<", +"<<k<<" , yes : "<<dp[i][l][k][1]<<endl;
}
wall;
}
wall;wall;
}*/
/****/
for(int i=1; i<30; i++){
for(auto e : ve[i]){
int l=e.F , r=e.S;
if(dp[i][l][0][0]<INF){
seg[r].push_back({l,dp[i][l][0][0]});
}
if(dp[i][l][0][1]<INF){
seg[r].push_back({l,dp[i][l][0][1]});
}
}
}
mn[0] = 0;
for(int i=1; i<=n; i++)mn[i] = INF;
for(int i=1; i<=n; i++){
for(auto e : seg[i]){
int l = e.F , w = e.S;
mn[i] = min(mn[i] , mn[l-1]+w);
}
}
if(mn[n]==INF){
cout<<-1;
return 0;
}else cout<<mn[n];
return 0;
}
/**
10
1 1 1 1 2 2 2 3 2 1
*/
// ans = 5;
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:37:25: warning: unused variable 'r' [-Wunused-variable]
37 | int l=e.F , r=e.S , mid=l+(1ll<<(i-1));
| ^
Main.cpp:37:33: warning: unused variable 'mid' [-Wunused-variable]
37 | int l=e.F , r=e.S , mid=l+(1ll<<(i-1));
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
