第一届程序设计竞赛题解（K题）

题目描述：

瑟提是一个拳击高手，蓄意轰拳是他一个非常强大的技能。
一天，他碰到个 N 个敌人。因为敌人都排好队了，所以，我们可以将问题简单化，瑟提每次蓄意轰拳可以使连续3个位置上的敌人遭到 1 点伤害。（也可以只对 一个敌人 或者 相邻的两个敌人 造成伤害）
当敌人的血量变为 0 时，视为敌人被消灭（但敌人的位置仍然保留）。
此外瑟提还具有一个大招——叹为观止！(只能使用一次)
他可以让两个相邻的敌人直接消灭（只有一个敌人也可以使用，敌人位置仍然保留）。
瑟提不想浪费体力，所以他只会使用蓄意轰拳和叹为观止。
请问，瑟提最少需要使出多少次蓄意轰拳，才能够消灭所有敌人？
如果瑟提太晚回家，他的老妈会担心他，为了不让瑟提的老妈担心，瑟提请聪明的你来帮助他！

输入描述：

第一行一个数 n (1 <= n <= 10⁶)，分别表示敌人的数量
第二行共 n 个整数，第 i 个整数表示 a_i (0 <= a_i <= 10⁹) 表示第 i 只敌人的血量

输出描述：

共一个数，表示瑟提最小需要使出蓄意轰拳的次数

示例：

输入：
3
66 66 1
输出：
1
说明：
对 1 号敌人和 2 号敌人使用叹为观止，对 3 号敌人使用一次蓄意轰拳。

思路：
使用两次前缀和，一次从前往后，一次从后往前，比较两次前缀和的值，取最小的结果。所以先将输入数据复制为 a[ ] 数组和 b[ ] 数组两个，分别求前缀和。
如果敌人数量小于等于2，直接使用大招叹为观之，无需使用蓄意轰拳，输出0。因为每次蓄意轰拳可以使连续3个位置上的敌人遭到 1 点伤害，我们在每次计算前缀和后，需要将后两个敌人减去该敌人的值，表示对该敌人使用几次蓄意轰拳，则后两个敌人同样会遭受相同的伤害，直至该敌人血量变为0。所以每次前缀和前还需要判断该敌人血量是否大于0，大于0则重复前缀和，小于等于0则前缀和值不变，继续下一个敌人。

AC代码如下：

#include 
#define ll long long
using namespace std;
const int N = 1e6+10;
 
int a[N], b[N];
ll suma[N];//从头开始的前缀和
ll sumb[N];//从尾开始的前缀和
ll ans;
 
int main(){
	//初始化
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++){
        //cin >> a[i];
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
 
    //小于等于2，直接使用大招叹为观止，无需使用蓄意轰拳
    if (n <= 2){
        cout << "0" << endl;;
        return 0;
    }
 
    //从头开始的前缀和
    for (int i = 1; i <= n; i++){
        if (a[i] > 0){
            suma[i] = a[i] + suma[i-1];
            //后两个敌人遭受同等伤害
            a[i+1] -= a[i];
            a[i+2] -= a[i];
        }
        else
            suma[i] = suma[i-1];
    }
 
    //从尾开始的前缀和
    for (int i = n; i >= 2; i--){
        if (b[i] > 0){
            sumb[i] = sumb[i+1] + b[i];
            //前两个敌人遭受同等伤害
            b[i-1] -= b[i];
            b[i-2] -= b[i];
        }
        else
            sumb[i] = sumb[i+1];
    }
 
    ans = suma[n];
    for (int i = 1; i <= n; i++){
    	//每次比较得出最小的值
        ans = min(suma[i-1] + sumb[i+2], ans);
    }
 
    cout << ans << endl;
 
    return 0 ;
}