hdu 1024 Max Sum Plus Plus 最大m个子序列

传送门: http://acm.hdu.edu.cn/showproblem.php?pid=1024

• 题意
  最大m个子序列
• dp
  dp[divid][now] = max(dp[divid-1][1~now-1], dp[divid-1][now-1])+array[now];
• 解释:
  now 是选择第 now 个, divid 是前 now 个分为 divid 个序列.
• 数据范围 1e6
  dp[1e6][1e6] == mle
• 降维
  降维真不是人干的活2333333
  发现每一个元素只用了几次, 有贡献的永远是最大值, 所以开个tmax记录当前divid的max, 滚动下
  不清楚为啥divid = 1 的时候会wa, 大概是写挫了, 懒得改于是divid = 1 特判好了

#include <stdio.h>
#include <iostream>
#include <cstring>
using namespace std;
const int MAX = 1e6+10;
const long long INF = 1e15+10;
long long dp[MAX], ary[MAX], n, m, itor, tmax, nxt, last, ans;
long long mmax (long long a, long long b) {
    return a > b ? a : b;
} 
bool getin() {
    if (scanf("%lld%lld", &m, &n) == 2) {
        for (int i = 0; i < n; ++i)
            scanf("%lld", ary+i);
        memset (dp, 0, sizeof(dp));
        return true;
    }
    return false;
}
void judge() {
    for (int divid = 1; divid <= m; ++divid) {
        for (int now = divid-1; now < n; ++now) {
            if (divid == 1) {
                if (!now) 
                    tmax = mmax(0, ary[0]), dp[now] = ary[0];
                else 
                    dp[now] = mmax(dp[now-1]+ary[now], ary[now]);
            }
            else {
                if (now == divid-1)
                    tmax = dp[now-1];
                nxt = mmax(tmax, dp[now]);
                dp[now] = mmax(tmax, dp[now-1])+ary[now];
                tmax = nxt;
            }
// printf("%cdp[%d] = %lld", "\n "[(bool)(now-divid+1)], now, dp[now]);
        }
    }
    ans = -INF;
    for (int i = m-1; i < n; ++i) 
        ans = mmax(ans, dp[i]);
    printf("%lld\n", ans);
}
int main() {
    freopen("in.t", "r", stdin);
    freopen("out.t", "w", stdout);
    while( getin()) {
        judge();
    }
    return 0;
}

2017-09-06