Algoogle

Algorithm for Programming Contest

Typical DP Contest L - 猫

Category: TDPC Tag: dp

L - 猫

問題概要


解法


ある猫iから距離1以内にいる1番左の猫をl[i]とすると,lは単調非減少.
dp[i][j] := 猫iまででiの距離1以内にいる一番左の猫がjのときの最大値
とすると

と更新できる.これはjを順に見ていけばそれぞれO(1)で計算可能.

コード


(L.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repi(i,0,n)

const int inf = 1e9;
int n, f[1024][1024], dp[1024][1024], sum[1024][1024];

int solve() {
    rep(i,n) rep(j,n) sum[i][j+1] = sum[i][j]+f[i][j];
    repi(i,1,n) {
        int m = -inf;
        rep(j,i+1) {
            m = max(m, dp[i-1][j]);
            dp[i][j] = m+sum[i][i]-sum[i][j];
        }
    }
    int ans = -inf;
    rep(i,n) ans = max(ans, dp[n-1][i]);
    return ans*2;
}

void input() {
    scanf("%d", &n);
    rep(i,n) rep(j,n) scanf("%d", f[i]+j);
}

int main() {
    input();
    printf("%d\n", solve());
    return 0;
}

Comments