hdu4561 bjfu1270 最大子段积

就是最大子段和的变体。最大子段和只要一个数组,记录前i个里的最大子段和在f[i]里就行了,但是最大子段积因为有负乘负得正这一点,所以还需要把前i个里的最小子段积存起来。就可以了。直接上代码:

/*
 * Author    : ben
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
//输入非负整数,用法int a = get_int();
int get_int() {
    int res = 0, ch;
    while (!((ch = getchar()) >= '0' && ch <= '9')) {
        if (ch == EOF)
            return -1;
    }
    res = ch - '0';
    while ((ch = getchar()) >= '0' && ch <= '9')
        res = res * 10 + (ch - '0');
    return res;
}
//输入整数(包括负整数,故不能通过返回值判断是否输入到EOF,本函数当输入到EOF时,返回-1),用法int a = get_int2();
int get_int2() {
    int res = 0, ch, flag = 0;
    while (!((ch = getchar()) >= '0' && ch <= '9')) {
        if (ch == '-')
            flag = 1;
        if (ch == EOF)
            return -1;
    }
    res = ch - '0';
    while ((ch = getchar()) >= '0' && ch <= '9')
        res = res * 10 + (ch - '0');
    if (flag == 1)
        res = -res;
    return res;
}

const int MAXN = 19;
int maxr[MAXN], minr[MAXN];

inline int mymul(int a, int b) {
    int sign = 1;
    if (a * b == 0) {
        return 0;
    }
    if (a * b < 0) {
        sign = -1;
    }
    return sign * (abs(a) + abs(b));
}

int main() {
    int T = get_int(), tmp, N;
    int a[3];
    for (int t = 1; t <= T; t++) {
        N = get_int();
        maxr[0] = minr[0] = 0;
        int ans = 0;
        for (int i = 1; i <= N; i++) {
            tmp = get_int2() / 2;
            a[0] = mymul(maxr[i - 1], tmp);
            a[1] = mymul(minr[i - 1], tmp);
            a[2] = tmp;
            sort(a, a + 3);
            maxr[i] = a[2];
            ans = maxr[i] > ans ? maxr[i] : ans;
            minr[i] = a[0];
        }
        printf("Case #%d: %d\n", t, ans);
    }
    return 0;
}

 

更多相关文章
  • 原题链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1050 如果没有循环的条件,那么我们可以用常规的方法算出最大的字段和max1 然后加上循环这个条件,我们可以先求出整个数组的和,然后在求出数组最小子段和,然后然后相
  • 最大子段和 Time Limit:1MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u   Description Given a sequence a[1],a[2],a[3]......a[n], your job ...
  • 题目意思还是很好理解的,在一个数列中,找出不相交的两个子串使得其和最大. 解题思路: 对于每个i来说,求出[0 ~ i - 1] 的最大子段和以及[i ~ n - 1]的最大子段和,在加起来,求最大的一个就行了. [
  • 题目链接: http://xcacm.hfut.edu.cn/problem.php?id=1103 题目大意:链更新.链查询,求树链的最大子段和.(子段可以为空) 解题思路: 将所有Query离线存储,并且注明哪个
一周排行