Date:January 29th Title: 集训Day2-小信小友打怪兽 题解

时间：1s 空间：256M

题目描述：

小信与小友一起组队打怪兽。有一个长度为n的怪兽序列，一些怪兽会对小信造成伤害，另一些不会；小友是大佬，所有怪兽都伤害不了他。小信与小友轮流打怪兽，小信先手，小友后手，他们需要按照顺序打怪兽。由于技能有冷却时间，每次每个人最多打两只怪兽，至少打一只怪兽。问小信最少会受到几只怪兽的伤害。

例如有8只怪物"1 0 1 1 0 1 1 1"，1表示这只怪兽会对小信造成伤害，0表示不会对小信造成伤害。

第一回合，小信打第1只与第2只怪兽，受到第1只怪兽的伤害；小友打第3只与第4只。

第二回合，小信打第5只怪兽；小友打第6只与第7只。

第三回合，小信打第8只怪兽，并受到伤害。

游戏结束，小信总共受到了2只怪兽的伤害。

输入格式：

第一行包含一个正整数 n，表示序列长度。

第二行包含长度为 n 的01序列。

输出格式：

输出一个整数表示答案。

样例输入：

8

1 0 1 1 0 1 1 1

样例输出：

2

约定：

对于30的数据，n 不超过 10。

对于50的数据，n 不超过 500。

对于100的数据，n 不超过 106。

题意：

小信和小友打怪兽，轮流打一只或两只，部分怪兽会对小·信造成伤害，问能让小信受伤最少的方案.

分析：

这题是一道动态规划，首先读入你，输入每个怪兽是否有伤害，然后然后用dfs查出结果，终止条件是打怪的次数大于怪兽的数量了，然后进行选择。

Code：

#include <bits/stdc++.h>
using namespace std;
int a,n[1000005],minn=INT_MAX;
int t[1000005][2];
int dfs(int last,int player)
{
    if(last>a)return 0;;
    int ret=INT_MAX;
    if(t[last][player]<1000005)return t[last][player];
    if(player==1)
    {
        ret=min(ret,dfs(last+1,0));
        if(last!=a)ret=min(ret,dfs(last+2,0));
    }
    else{
        ret=min(ret,dfs(last+1,1)+n[last]);
        if(last!=a)
            ret=min(ret,dfs(last+2,1)+n[last]+n[last+1]);
    }
    return t[last][player]=ret;
}
int main()
{
    cin>>a;
    for(int i=1;i<=a;i++)
    {
        cin>>n[i];
    }
    for(int i=0;i<1000005;i++)
    {
        for(int j=0;j<2;j++)
        {
            t[i][j]=INT_MAX;
        }
    }
    cout<<dfs(1,0);
}

The End