HDU_1024

    可以用f[i][j]表示扫描到第j个元素时且一共选i个区间的最优解，这样可以得到f[i][j]=max{f[i][j-1],f[i-1][k]+A[j]-A[k]}(i-1<=k<j)，其中A[]表示前缀和。

    如果不加优化的话是O(MN^2)的算法，但实际上我们可以在递推的过程中维护x=f[i-1][k]-A[k]的最大值，那么动态转移方程就改写成了f[i][j]=max{f[i][j-1],x+A[j]}，这样就是O(MN)的复杂度。

    此外，为了节约空间，可以使用滚动数组。

#include
     
       #include
      
        #define MAXD 1000010 #define INF 1000000000000000ll int N, M; long long int A[MAXD], wa[MAXD], wb[MAXD], *a, *b; void init() {
   int i, j, k;     A[0] = 0; for(i = 1; i <= N; i ++)     {
           scanf("%d", &k);         A[i] = A[i - 1] + k;     } } void solve() {
   int i, j, k; long long int *t, x;     a = wa, b = wb; for(i = 0; i <= N; i ++)         b[i] = 0; for(i = 1; i <= M; i ++)     {
           a[i - 1] = -INF;         x = b[i - 1] - A[i - 1]; for(j = i; j <= N; j ++)         {
               a[j] = a[j - 1]; if(x + A[j] > a[j])                 a[j] = x + A[j]; if(b[j] - A[j] > x)                 x = b[j] - A[j];         }         t = a, a = b, b = t;     }     printf("%I64d\n", b[N]); } int main() {
   while(scanf("%d%d", &M, &N) == 2)     {
           init();         solve();     } return 0; }