HDU1024 고급 압축 기능...선진적인 나는 강에 뛰어들고 싶다

Description
Now I think you have got an AC in Ignatius.L’s “Max Sum” problem. To be a brave ACMer, we always challenge ourselves to more difficult problems. Now you are faced with a more difficult problem.
Given a consecutive number sequence S 1, S 2, S 3, S 4 … S x, … S n (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ S x ≤ 32767). We define a function sum(i, j) = S i + … + S j (1 ≤ i ≤ j ≤ n).
Now given an integer m (m > 0), your task is to find m pairs of i and j which make sum(i 1, j 1) + sum(i 2, j 2) + sum(i 3, j 3) + … + sum(i m, j m) maximal (i x ≤ i y ≤ j x or i x ≤ j y ≤ j x is not allowed).
But I`m lazy, I don’t want to write a special-judge module, so you don’t have to output m pairs of i and j, just output the maximal summation of sum(i x, j x)(1 ≤ x ≤ m) instead. ^_^
Input
Each test case will begin with two integers m and n, followed by n integers S 1, S 2, S 3 … S n. Process to the end of file.
Output
Output the maximal summation described above in one line.
Sample Input
1 3 1 2 3 2 6 -1 4 -2 3 -2 3
Sample Output
6 8
이 문제의 대의는 바로 너에게 한 조의 수를 준 다음에 너에게 몇 개의 서열을 만들어서 그의 것과 가장 큰 것을 알려주는 것이다.좋아, 이 문제는 처음에 나는 상태 이동 방정식도 생각하지 못했는데 나중에 가까스로 dp[a][b]=max(dp[a][b-1]+zhi[b],max(dp[a-1])+zhi[b])라는 방정식을 생각해냈다.바로 dp가 대표하는 의미는 b를 끝으로 하는 서열과......이 물건은 1에서 순환하기 시작하기 때문에 그것의 연속성은 보장되어 있다. 그의 뒤에 있는 그 물건은 바로 앞의 a-1자 서열의 최대와...얘가 연속이 되든 안 되든 더하면 되잖아...어쨌든 서열이 하나가 모자라서 마침 잘 됐어요. 그런데 문제가 또 생겼어요. 이 n은 백만 원이에요. n은 백 퍼센트예요. 이 공간의 복잡도가 하늘까지 치솟을 거예요. 그리고 저는 멍해져서 쿠앙빈 대신의 문제를 봤어요. 이 2차원 그룹을 1차원 그룹으로 압축하는 대단한 방법이 있더라고요.우선 우리는 이 층수를 알 수 있다. 기껏해야 두 번을 사용하고 첫 번째는 기록한다. 두 번째는 좌석의 한 층에서 사용한다. 그리고 우리는 상태 전이 방정식을 통해 전이될 방정식을 알 수 있다. 그것은 맥스의 첫 번째 층수와 그의 층수가 완전히 같다는 것을 알 수 있다. 그러면 문제를 줄일 수 있다. 두 번째 수는 바로 쿠앙빈 대신의 독특한 점이다.그가 먼저 앞의 수를 사용한 것은 윗층의 최대를 나타낸다. 다 쓴 후에 갱신한다. 이렇게 각 층이 다 쓴 후에 갱신하는 값은 이 층의 작문 아래 층의 윗층을 사용해서 사용하는 것이다. 나 같은 지능의 곤충은 세 개의 수조만 따면 충분하다고 생각하지만 이 순환 불변식은 내가 쓸 수 없다.그리고 마지막 층까지 순환할 때 마지막 층을 엉뚱한 층의 상층으로 갱신합니다.. 그래서 그 맥스x는 당연히 최대치가 됩니다...
또 하나 주의해야 할 것은... 바로 내부 순환은 반드시 외부 순환의 값부터 시작해야 한다는 것이다. 왜냐하면 너의 수가 층수보다 적을 수는 없기 때문이다... 마드 미친 WA가 더 무서운 것은 이 문제가long long으로 시간을 초과할 것이다!!!!!!이것은 나를 놀리는 것이 아니냐

#include
#include
#include
using namespace std;
int   dp[1000010];
int  da[1000011];
int  zhi[1000011];
#define INF 0x7fffffff
int main()
{
    int  n,m;
    while (cin >> n >> m)
    {
        memset(dp, 0, sizeof(dp));
        memset(da, 0, sizeof(da));
        for (int a = 1;a <= m;a++)scanf("%d", &zhi[a]);
        int  maxx = 0;
        for (int a = 1;a <=n;a++)
        {
            maxx = -INF;
            for (int b = a;b<=m;b++)
            {
                dp[b] = max(dp[b - 1] + zhi[b], da[b-1] + zhi[b]);//     b        
                da[b - 1] = maxx;//       ，                     b      
                maxx = max(maxx, dp[b]);//  ，              ，            ，      ；
            }
        }
        cout << maxx << endl;
    }
    return 0;
}