1 solutions

  • 0
    @ 2025-12-27 10:33:36
    #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