5721번: 사탕 줍기 대회

https://www.acmicpc.net/problem/5721


$O(tmn)$

최적해에 해당하는 어떤 수를 선택했을 때 해당 수와 같은 행에서 인접하지 않는 최대합이 되도록 다른 수들도 선택되어 있을 것이다.
어떤 행에 있는 수열을 {ai}라 하자.
dp[i]: 1~i 번째 항들 중 인접하지 않게 선택해서 만든 합의 최댓값
그러면
dp[0]=0
dp[i]=max(dp[i-1],dp[i-2]+ai)가 성립한다.

이를 이용해 i번째 행의 dp[m]을 다시 ai라고 정의해보자.
위 수열 {ai}에 대한 점화식을 풀고나면 전체해를 구할 수 있다.

#include<cstdio>
#include<algorithm>
using namespace std;
int m, n, x[100001], y[100001];
int main() {
    while (scanf("%d%d", &m, &n) && m) {
        for (int i = 1; i <= m; i++) {
            for (int j = 1, t; j <= n; j++) {
                scanf("%d", &t);
                y[j] = max(y[j - 2] + t, y[j - 1]);
            }
            x[i] = max(x[i - 2] + y[n], x[i - 1]);
        }
        printf("%d\n", x[m]);
    }
    return 0;
}