HDU 1024 Max Sum Plus Plus（DP的简单优化）

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

const int INF=0x3f3f3f3f;
const int maxn=1e6+5;
int f[maxn], pre[maxn], a[maxn];

int main()
{
    //freopen("in.txt", "r", stdin);
    int m,n;
    while(cin>>m>>n)
    {
        for(int i=1; i<=n; i++)
            cin>>a[i];

        memset(f, 0, sizeof(f));
        memset(pre, 0, sizeof(pre));
        
        int tmax;
        for(int i=1; i<=m; i++)
        {
            tmax=-INF;
            for(int j=i; j<=n; j++)
            {
                f[j]=max(f[j-1], pre[j-1])+a[j];
                pre[j-1]=tmax;  //注意pre的更新的顺序，pre[j-1]被使用后再更新pre[j-1]
                tmax=max(tmax, f[j]);
            }
        }
        cout<<tmax<<endl;
    }
    return 0;
}