1 solutions
-
0
#include<bits/stdc++.h> using namespace std; #define int long long int dp[600005][2]; int sz[600005]; signed main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>sz[i]; sz[i+n]=sz[i]; } memset(dp,0x7f,sizeof(dp)); int ans=1000000000000; dp[1][1]=sz[1]; for(int i=2;i<=n;i++){ dp[i][0]=dp[i-1][1]; dp[i][1]=min(dp[i-1][1],dp[i-1][0])+sz[i]; } ans=min(dp[n][1],dp[n][0]); memset(dp,0x7f,sizeof(dp)); dp[n][1]=sz[n]; for(int i=n+1;i<=2*n-1;i++){ dp[i][0]=dp[i-1][1]; dp[i][1]=min(dp[i-1][1],dp[i-1][0])+sz[i]; } ans=min(ans,min(dp[2*n-1][1],dp[2*n-1][0])); cout<<ans; }
- 1
Information
- ID
- 832
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 6
- Tags
- (None)
- # Submissions
- 25
- Accepted
- 10
- Uploaded By