洛谷 P3009 [USACO11JAN]利润Profits

题目传送门

解题思路:

一道很简单的DP,首先统计前缀和,用f[i]表示到第i个元素可以获得的最大利润,用一个变量k来储存在i之前能获得最大连续利润的序列的首元素,所以就推出了:

f[i]=max(f[i],sum[i]-sum[k-1]);  

关于k的更新: 当到了一个位置j,sum[j]-sum[k-1]<0时,就将k放入待定席,直到找到一个正数为止.

AC代码:

#include<iostream>
#include<cstdio>

using namespace std;

int n,sum[100001],f[100001],ans = -999999999,xb;
bool flag,vis;

int main() {
    scanf("%d",&n);
    for(int i = 1;i <= n; i++) {
        scanf("%d",&f[i]);
        sum[i] = f[i] + sum[i-1];
        f[i] = max(f[i],sum[i] - sum[xb-1]);
        ans = max(ans,f[i]);
        if(sum[i] - sum[xb-1] < 0) {
            flag = 1;
            xb = i;
        }
        if(flag == 1 && sum[i] - sum[xb-1] > 0) {
            flag = 0;
            xb = i;
        }
    }
    printf("%d",ans);
    return 0;
}