题目描述

You and your friend are playing the game Mortal Kombat XI. You are trying to pass a challenge tower. There are n bosses in this tower, numbered from 1 to n. The type of the i-th boss is ai. If the i-th boss is easy then its type is ai=0, otherwise this boss is hard and its type is ai=1.

During one session, either you or your friend can kill one or two bosses (neither you nor your friend can skip the session, so the minimum number of bosses killed during one session is at least one). After your friend session, your session begins, then again your friend session begins, your session begins, and so on. The first session is your friend’s session.

Your friend needs to get good because he can’t actually kill hard bosses. To kill them, he uses skip points. One skip point can be used to kill one hard boss.

Your task is to find the minimum number of skip points your friend needs to use so you and your friend kill all n bosses in the given order.

For example: suppose n=8, a=[1,0,1,1,0,1,1,1]. Then the best course of action is the following:

your friend kills two first bosses, using one skip point for the first boss;
you kill the third and the fourth bosses;
your friend kills the fifth boss;
you kill the sixth and the seventh bosses;
your friend kills the last boss, using one skip point, so the tower is completed using two skip points.
You have to answer t independent test cases.
Input
The first line of the input contains one integer t (1≤t≤2⋅104) — the number of test cases. Then t test cases follow.

The first line of the test case contains one integer n (1≤n≤2⋅105) — the number of bosses. The second line of the test case contains n integers a1,a2,…,an (0≤ai≤1), where ai is the type of the i-th boss.

It is guaranteed that the sum of n does not exceed 2⋅105 (∑n≤2⋅105).

Output
For each test case, print the answer: the minimum number of skip points your friend needs to use so you and your friend kill all n bosses in the given order.

样例

6
8
1 0 1 1 0 1 1 1
5
1 1 1 1 0
7
1 1 1 1 0 0 1
6
1 1 1 1 1 1
1
1
1
0

2
2
2
2
1
0

比赛时候没有看到这个题，赛后补题时候才发现这是一个非常好的思维dp
首先，题目大意是我和朋友杀怪物，朋友杀不了困难怪，杀困难怪要用到技能点，我和朋友交替的杀
给定怪的难度求出使用技能点的最小值，很简单，就像爬楼梯那样转换 我这里介绍俩种解法
第一种2个dp数组
dp_i表示我杀了第i只怪物朋友所使用技能点数的最小值
dp_f表示朋友杀了第i只怪物朋友使用的技能点最小值
所以 我的状态转移方程就是 dp_i[i]=min(dp_f[i-1],dp_f[i-2])
所以 朋友的状态转移方程就是 dp_f[i]=min(dp[i-1]+a[i],dp[i-2]+a[i-1]+a[i]);
然后初始化 为 dp_f[1]=a[1],dp_f[2]=a[1]+a[2];
因为我是不可以先杀怪兽的 所以我的初始化可以先初始化一个比较大的值 或者是 在用到dp[1]的时候特判一下 dp_i[1]=0x3f3f3f3f,dp_i[2]=dp_f[1];
最后输出答案时候，因为最后一只怪兽可能是我杀死的也可能是朋友杀死的，所以要在dp_i,dp_f中取得最小值

#include<bits/stdc++.h>
const int maxn = 2e5+10;
using namespace std;
int a[maxn],dp_i[maxn],dp_f[maxn],n,t;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        if(n==1) cout<<a[1]<<endl;
        else if(n==2) cout<<a[1]<<endl;//这里就是我杀一个让朋友不用技能更好
        else{
            dp_f[1]=a[1],dp_f[2]=a[1]+a[2];
            dp_i[1]=0x3f3f3f3f,dp_i[2]=dp_f[1];
            for(int i=3;i<=n;i++)
            {
                dp_i[i]=min(dp_f[i-1],dp_f[i-2]);
                dp_f[i]=min(dp_i[i-2]+a[i-1]+a[i],dp_i[i-1]+a[i]);
            }
            int ans=min(dp_i[n],dp_f[n]);
            cout<<ans<<endl;
        } 
    }
    return 0;
}

第二种其实是建立在第一种得优化
把dp_i数组用dp_f来统一表示
因为
dp_i[i-1]=min(dp_f[i-2],dp_f[i-3])
dp_i[i-2]=min(dp_f[i-3],dp_f[i-4])
带入dp_f得状态转移方程得到
dp_f[i]=min(min(dp_f[i-2]+a[i],dp_f[i-3]+a[i]),min(dp_f[i-3]+a[i-1]+a[i],dp_f[i-4]+a[i-1]+a[i]))
dp_f就可以由第i-2,第i-3,第i-4推过来
第i-2就是代表我在中间杀了一个
第i-4就是每个人都杀了2个
第i-3就是我杀了一个或者2个
然后就是其初始化了
要判断每个条件是否合法
所以得
dp_f[1]=a[1];dp_f[2]=a[1]+a[2];
dp_f[3]=dp_f[1]+a[3];
dp_f[4]=min(dp_f[1]+a[3]+a[4],min(dp_f[2]+a[4],dp_f[1]+a[4]));
i从5开始枚举后面得情况
但是要注意一下输出
最后一个可能是朋友杀得
那就是 dp_f[n]
可能是我杀了一个
dp_f[n-1]
可能我杀了2个
dp_f[n-2]
所以在3者取最小就ok了

#include<bits/stdc++.h>
const int maxn = 2e5+10;
using namespace std;
int a[maxn],dp_i[maxn],dp_f[maxn],n,t;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        if(n==1) cout<<a[1]<<endl;
        else if(n==2) cout<<a[1]<<endl;//这里就是我杀一个让朋友不用技能更好
        else{
            dp_f[1]=a[1],dp_f[2]=a[1]+a[2];
            dp_f[3]=dp_f[1]+a[3];
            dp_f[4]=min(dp_f[1]+a[3]+a[4],min(dp_f[2]+a[4],dp_f[1]+a[4]));
            for(int i=5;i<=n;i++)
            {
                //dp_i[i]=min(dp_f[i-1],dp_f[i-2]);
                dp_f[i]=min(min(dp_f[i-3]+a[i-1]+a[i],dp_f[i-4]+a[i-1]+a[i]),min(dp_f[i-2]+a[i],dp_f[i-3]+a[i]));
            }
            int ans=min(min(dp_f[n],dp_f[n-1]),dp_f[n-2]);
            cout<<ans<<endl;
            }

        }
        return 0; 
    }