SDUT 3100 动态规划?(动态规划)解题报告

2016-02-16 1,352 次浏览 解题报告

题面

动态规划?
Time Limit: 1000ms Memory limit: 65536K

题目描述
动态规划作为《运筹学》的一个分支,被广泛的用于解决较为复杂的经济管理问题,以达到的最优抉择,获得最大经济收益为目的。也因其多变性,非常的频繁的出现在信息学竞赛的赛场上。
动态规划的核心思想为不断将问题分解为子问题,一直到可以较容易的得到最优答案,再去决定其父问题的决策,因为很大程度的避免了重复子问题的抉择,故可以节约大量时间。

现在问题来了,有一个一维数组,存储了n个正整数,下标依次为0,1,2,….,n-1。
现在要从中选取一部分数,你要给出一个选择方案使得你的方案满足下列要求:

  1. 这部分元素的下标应满足st,st+5, st+52 , st+53, … , st+5x (0 <= st < n ,st <= st+5x < n)。
  2. 在满足第一条要求的方案中,应选取其累加和最大的一种的方案。

输入
多组输入。
对于每组输入:
第一行输入一个n(1 <= n <= 100000)。
接下来的一行有n个整数y(-100000 <= y <= 100000)。

输出
对于每组数据,输出一个整数代表你的方案的累加和。

示例输入
10
1 2 3 4 5 6 7 8 9 10
3
1 -10 2
3
-1 -2 -3

示例输出
15
2
-1

提示

来源
zmx

解题思路

这道题是典型的求最大连续子序列和的问题。其求法可以参考我的这篇文章

理解了最大连续子序列和的算法,这道题就不难解决了。由于每种方案的元素下标都满足 st + 5*n,因此我们可以把 st 从 0 到 4 的一共 5 种方案看作 5 个可找到的最长序列,对每个序列求其最大连续子序列和,最后再从这 5 个最大连续子序列和中找出最大的即得到结果。

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

#include <cstdio>
using namespace std;

int n, a[100000];

int Solve(int st);

int main(int argc, char const *argv[]) {
    while(~ scanf("%d", &n)) {
        for(int i=0; i<n; ++i) {
            scanf("%d", &a[i]);
        }
        int max_sum = Solve(0), sum;
        //遍历所有 st,并且应注意 n < 5 的情况
        for(int i=1; i<5 && i<n; ++i) {
            sum = Solve(i);
            if(sum > max_sum)
                max_sum = sum;
        }
        printf("%d\n", max_sum);
    }
    
    return 0;
}

//求最大连续子序列和
int Solve(int st) {
    int max_sum = -100000, this_sum = 0;
    for(int i=st; i<n; i+=5) {
        this_sum += a[i];
        if(this_sum > max_sum)
            max_sum = this_sum;
        if(this_sum < 0)
            this_sum = 0;
    }

    return max_sum;
}

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

还不快抢沙发

添加新评论