题目大意
分析
我们不难整个线段可以被划分为5段
我们设路径到达的最左的地方是L,最右的地方是R
则这五段分别是0~L,L+1~S,S+1~T,T+1~R,R+1~N
最外面的两端不经过,所以花费为a[i]
S+1~T这一段只能通过奇数次,剩余两段只能通过偶数次
所以这三段的答案均与奇偶性有关系
因此我们可以得到dp[i][0/1/2/3/4]表示现在考虑到第i个点,这个点属于第1/2/3/4/5段时的最优解
转移非常简单，详见代码
代码
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<cctype> #include<cmath> #include<cstdlib> #include<queue> #include<ctime> #include<vector> #include<set> #include<map> #include<stack> using namespace std; #define int long long const int inf = 1e16+7; int dp[200100][5],a[200100]; inline int wh2(int x){ if(x==0)return 2; return x%2; } inline int wh1(int x){ if(x==0)return 1; return (x%2)^1; } signed main(){ int n,m,i,j,k; scanf("%lld",&n); for(i=1;i<=n;i++)scanf("%lld",&a[i]); for(i=1;i<=n;i++) for(j=0;j<5;j++) dp[i][j]=inf; for(i=0;i<5;i++)dp[0][i]=0; for(i=1;i<=n;i++){ int wh=dp[i-1][0]; dp[i][0]=wh+a[i]; wh=min(wh,dp[i-1][1]); dp[i][1]=wh+wh2(a[i]); wh=min(wh,dp[i-1][2]); dp[i][2]=wh+wh1(a[i]); wh=min(wh,dp[i-1][3]); dp[i][3]=wh+wh2(a[i]); wh=min(wh,dp[i-1][4]); dp[i][4]=wh+a[i]; } cout<<min(dp[n][2],min(dp[n][3],dp[n][4]))<<endl; return 0; }