Codeforces Round #620 F2. Animal Observation(hard version)(dp + 세그먼트 트리)

Codeforces Round #620 F2. Animal Observation(hard version)(dp + 세그먼트 트리)

제목 링크

제목의 뜻

nm의 행렬을 정하고 줄마다 2k의 행렬을 취하여 총 행렬의 수와 최대치를 구하고 반복해서 얻은 수는 계산하지 않는다

문제풀이

dp[i]는 현재 줄이 i 개수부터 행렬의 최대 값을 가져옴을 나타냅니다.

dp[i] = 이전 줄의 최대 수 + 현재 줄의 i개수 i+k-1개수와 - 현재 줄이 중복된 + 다음 줄의 i개수 i+k-1개수와

라인 트리로 이전 줄의 최대 수 + 현재 줄의 i 개수 i+k-1 개수와 - 현재 줄이 중복된

현재 줄의 첫 번째 수부터 이전 줄의 dp값에 대해 상술한 조작을 하고 오른쪽으로 한 수를 옮길 때마다 dp를 한다. 현재 구간의 두미 삭제와 증가 조작만 하면 구체적인 조작은 코드를 볼 수 있다.

#include 
using namespace std;
const int N = 50010;
int tree[N*4], upd[N*4], dp[N], a[101][N], pre[101][N];
void build(int x,int l,int r)
{
    if (l == r) tree[x] = dp[l];
    else 
    {
        int mid = (l + r) >> 1;
        build(x*2, l, mid);
        build(x*2+1, mid + 1, r);
        upd[x] = 0;
        tree[x] = max(tree[x*2], tree[x*2+1]);
    }
}
void add(int x, int l,int r,int ll,int rr,int v)
{
    if (ll > rr) return;
    if (ll <= 0) return;
    if (l == r)
    {
        tree[x] += v;
        return;
    }
    if (ll <= l && r <= rr)
    { 
        upd[x] += v;
        tree[x] += v;
    }
    else 
    {
        tree[x * 2] += upd[x];
        upd[x * 2] += upd[x];
        tree[x * 2 + 1] += upd[x];
        upd[x * 2 + 1] += upd[x];
        upd[x] = 0;
        int mid = (l + r) >> 1;
        if (ll <= mid) add(x * 2, l, mid, ll, rr, v);
        if (rr > mid) add(x * 2 + 1, mid + 1, r, ll, rr, v);
        tree[x] = max(tree[x * 2], tree[x * 2 + 1]);
    }
}
int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    k--;//j + k - 1 -> j + k,    
    for (int i = 1; i <= n; i++)
     for (int j = 1; j <= m; j++)
     {
         cin >> pre[i][j];
         a[i][j] = pre[i][j];
         pre[i][j] += pre[i][j - 1];
     }
    for (int j = 1; j + k <= m; j++)
     {
         dp[j] = pre[1][j + k] - pre[1][j - 1] + pre[2][j + k] - pre[2][j - 1];
     }
    for (int i = 2; i <= n; i++)
     {
         build(1,1,m-k);
         for (int j = 1; j <= k + 1; j++) add(1,1,m-k,j+1,m-k,a[i][j]);//     dp               
         dp[1] = tree[1] + pre[i+1][k+1];
         for (int j = 2; j + k <= m; j++)
         {
             add(1,1,m-k,1,j-1,a[i][j+k]);
             add(1,1,m-k,j+k+1,m-k,a[i][j+k]);//    a[i][j+k]   dp   a[i][j+k]
             add(1,1,m-k,j,m-k,-a[i][j-1]);
             add(1,1,m-k,1,j-k-2,-a[i][j-1]);//    a[i][j-1] dp  a[i][j-1]
             dp[j] = tree[1] + pre[i+1][j + k] - pre[i+1][j-1];
         }
     }
     build(1,1,m-k);
     cout << tree[1] << endl;
    // system("pause");
}