SDUT 3554 无尽走廊(动态规划)解题报告

2016-06-08 1,379 次浏览 解题报告

题面

硬币问题
Time Limit: 1000ms Memory limit: 65536K

题目描述
芳芳有N(1<=N<=1000)个硬币,这些硬币排成一列,有正有反。我们定义这样一种操作,把[l,r]区间上的硬币都翻过来(1<=l<=r<=N).
芳芳想知道经过一次这样的操作后,最多有多少正面朝上的。
1代表正面,0代表反面。
比如:0 1 0 三个数,把区间1-3进行操作,数字就会变成1 0 1 正面向上的个数为2.

输入
本题有多组测试数据,每组数据有两行.
第一行包含一个数字N. 第二行有N个数字,1表示正面,0表示反面.

输出
每组数据输出一行.

示例输入
4
1 0 0 1

示例输出
4

提示

来源
第六届山东理工ACM网络编程擂台赛决赛

解题思路

这道题是典型的求最大连续子序列和的问题。我们首先回顾一下动态规划法求最大连续子序列和的方法:

int max_sum = 0, this_sum = 0;
for(int i=0; i<n; ++i) {
    this_sum += a[i]; //向右累加
    if(this_sum > max_sum) //更新最大子序列和
        max_sum = this_sum;
    if(this_sum < 0) //如果当前子序列和为负
        this_sum = 0; //则抛弃当前子序列
}

参照以上代码,我们举一个例子来说明:
对于序列 3 -2 4 -6 5 1,
遍历到 3 时:当前子序列为 3,this_sum = 3,max_sum = 3;
遍历到 -2 时:当前子序列为 3 -2,this_sum = 1,max_sum = 3;
遍历到 4 时:当前子序列为 3 -2 4,this_sum = 5,max_sum = 5;
遍历到 -6 时:当前子序列为 3 -2 4 -6,this_sum = -1,此时当前子序列和为负,如果不抛弃当前子序列而继续累加的话,下次的子序列和等于下一个元素加上一个负数,即 -1 + 5 = 4 < 5,必然比直接从下一个元素开始重新计算的子序列和要小,故抛弃当前子序列和,从下一个元素开始重新计算子序列和。this_sum = 0,max_sum = 5;
遍历到 5 时:当前子序列为 5,this_sum = 5,max_sum = 5;
遍历到 1 时:当前子序列为 5 1,this_sum = 6,max_sum = 6;
故得到结果为 6。

回到硬币问题上来,我们可以把翻硬币的过程相对初始状态比较,反面翻到正面就是正面的个数 +1,而正面翻到反面就是正面的个数 -1,因此我们可以把这个相对状态看作是一个由 1 和 -1 组成的序列,按照上面的方法求解即可。

这样我们就可以写出本题的代码了:

#include <cstdio>
using namespace std;

int main(int argc, char const *argv[]) {
    int n, a[1000];
    while(~ scanf("%d", &n)) {
        //sum 为初始状态的正面向上的硬币数
        int sum = 0;
        for(int i=0; i<n; ++i) {
            scanf("%d", &a[i]);
            if(a[i] == 1) sum++;
        }
        int max_sum = 0, this_sum = 0;
        for(int i=0; i<n; ++i) {
            if(a[i] == 0) //反面翻到正面看作 1
                this_sum++;
            else //正面翻到反面看作 -1
                this_sum--;
            if(this_sum > max_sum)
                max_sum = this_sum;
            if(this_sum < 0)
                this_sum = 0;
        }
        printf("%d\n", sum + max_sum);
    }
    
    return 0;
}

bLue 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。
本文地址:https://dreamer.blue/blog/post/2016/06/08/sdut-3554.dream

还不快抢沙发

添加新评论