[Atcoder Yahoo Contest 2019]D.Ears(动态规划)

Score:$600$ points

题面

传送门
翻译有时间再补…

题解

体验感极差，考试的时候手残把1打成了2Debug了半个小时,害的F题都没做。
先将题目转换一下:给你一条链,顺次连接着$n+1$个点，每条边有一个边权$A_i$，在有一个人从任意一个起点$P$出发，设他经过第$i$条边的次数$D_i$，求${\sum }_{i=1}^n|A_i+D_i|$的最小值。
首先需要证明一个结论:
A_i为奇数，等价于$A_i=1$。
A_i为大于0的偶数，等价于$A_i=2$。
证明很简单，可以发现走到边的同一侧的$D_i$奇偶性相同，由于你经过这条边的时候可以任意来回跳动偶数次，那么答案一定不会变的更劣。
考虑一个人从$P$点出发,有两种方案:
1.先往左边走，然后回到$P$点，再往右边走，不再回来。
2.先往右边走，然后回到$P$点，再往左边走，不再回来。
这很像一个dp。
定义状态$L{1}_i,L{2}_i,R{1}_i,R{2}_i$
分别代表从$i$点向左走需要回来的最小代价，从$i$点向左走不需要回来的最小代价，从$i$点向右走需要回来的最小代价，从$i$点向右走不需要回来的最小代价。

$$L1[i]=?\begin{array}{l}\min (L{1}_{i?1}+2,lsu{m}_i)(A_i==0)\\ \min (L{1}_{i?1}+1,lsu{m}_i)(A_i==1)\\ \min (L{1}_{i?1},lsu{m}_i)(A_i==2)\end{array}$$
$$L2[i]=?\begin{array}{l}\min (L{1}_i,min(L{2}_{i?1}+1,lsu{m}_i))(A_i==0)\\ \min (L{1}_i,min(L{2}_{i?1},lsu{m}_i))(A_i==1)\\ \min (L{1}_i,min(L{2}_{i?1}+1,lsu{m}_i))(A_i==2)\end{array}$$
R同理。
需要注意的是在走路的过程中可以随时不走后面的路调头，代价是前面/后面$i$个数的$A_i$之和。
答案就是$min(L1[i]+R2[i],L2[i]+R1[i])$。
时间复杂度:$O(n)$
[题解好像还有一种神仙写法，我菜爆了…]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
#define MAXN 200000
#define LL long long
#define DB double
#define FR first
#define SE second
int a[MAXN+5];
LL ans;
LL L1[MAXN],L2[MAXN+5],R1[MAXN+5],R2[MAXN+5];
LL lsum[MAXN+5],rsum[MAXN+5];
int n;
int get_num(int p)
{
    if(p==0)return 0;if(p%2==1)return 1;return 2;
}
int main()
{
    ans=1000000000;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++)lsum[i]=lsum[i-1]+a[i];for(int i=n-1;i>=0;i--)rsum[i]=rsum[i+1]+a[i+1];for(int i=1;i<=n;i++)a[i]=get_num(a[i]);for(int i=1;i<=n;i++){
    if(a[i]==0)L1[i]=min(L1[i-1]+2,lsum[i]);else if(a[i]==1)L1[i]=min(L1[i-1]+1,lsum[i]);else L1[i]=min(L1[i-1],lsum[i]);if(a[i]==0)L2[i]=min(L1[i],min(L2[i-1]+1,lsum[i]));else if(a[i]==1)L2[i]=min(L1[i],min(L2[i-1],lsum[i]));else L2[i]=min(L1[i],min(L2[i-1]+1,lsum[i]));}for(int i=n-1;i>=0;i--){
    if(a[i+1]==0)R1[i]=min(R1[i+1]+2,rsum[i]);else if(a[i+1]==1)R1[i]=min(R1[i+1]+1,rsum[i]);else R1[i]=min(R1[i+1],rsum[i]);if(a[i+1]==0)R2[i]=min(R1[i],min(R2[i+1]+1,rsum[i]));else if(a[i+1]==1)R2[i]=min(R1[i],min(R2[i+1],rsum[i]));else R2[i]=min(R1[i],min(R2[i+1]+1,rsum[i]));}for(int i=0;i<=n;i++){
    //printf("%d %lld %lld\n",i,L1[i]+R2[i],L2[i]+R1[i]);ans=min(ans,min(L1[i]+R2[i],L2[i]+R1[i]));}printf("%lld\n",ans);
}