SoundHound Inc. Programming Contest 2018 (春) D - 建物

• 問題

問題概要

HxWのグリッド,各グリッドに報酬p[i][j], コストc[i][j]が与えられる.
各グリッドに移動すると初回でp[i][j]が得られ, 毎回c[i][j]かかる. (i,j) -> (i+1,j), (i,j)+1, (i,j-1) への移動が可能であるとして(H,j) (1<=j<=W)に最終的にいる時の最大利益を求めよ.

解法

DPを3回ぐらいする.
完全にはまやんさんの解説通りにやったので,そんなに書くことがない...

ただいくつか自分がわかりにくいところがあったので書いておく.
a[i] := [0,i) で得られる利益 (解説だと1-indexed) について,

a_i = max(l<i)( sum(l<=j<i)(p_j - 2f_j) + f_l )
a(i+1) = max(l<i+1)( sum(l<=j<i+1)(p_j - 2f_j) + f_l ) = max( a_i + p_i - 2f_i (l<iの時), p(i+1) - f_(i+1) (l=iの時))

数式クソ見にくいけどはてなの数式クソだから仕方ないね.(ハマった)
b_iも同様に遷移する.

またdpの遷移も左から来る場合と下からそのまま来る場合を分ければわかる.

メモ

むずくない... DP苦手だ.
最初max_(3変数)で無理ってなったけど 結局下準備すれば解決する話だった.
あと,updateでのmaを使うみたいに分解する術を身につけた方が良さそう.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll lmod = 1e9+7,LINF=1LL<<60;
const int MAX_N = 50004;

using vl = vector<ll>;
using vll = vector<vl>;

int W,H;

vl update(const vl& dp,const vl& p,const vl& f){
  vl res(W,0LL),a(W,0LL),b(W,0LL);
  // a[i] := [0,i) で得られる利益
  rep(i,W-1) a[i+1] = max(a[i]+p[i]-2*f[i],p[i]-f[i]);
  // b[i] := (i,W-1] で得られる利益
  RREP(i,W-1,1) b[i-1] = max(b[i]+p[i]-2*f[i],p[i]-f[i]);
  
  ll ma = -LINF;
  rep(i,W){
    ma = max(ma+p[i]-f[i],dp[i]+p[i]-f[i]+max(a[i]-f[i],0LL));
    res[i] = ma + max(b[i]-f[i],0LL);
  }
  // 一緒だけどわかりにくいからmaを使った
  // res[0] = dp[0] + p[0] - f[0] + max(b[0]-f[0],0LL);
  // REP(i,0,W-1){
  //   res[i+1] = max(dp[i+1]+p[i+1]-f[i+1]+max(a[i+1]-f[i+1],0LL),
  //               res[i]+p[i+1]-f[i+1]-max(b[i]-f[i],0LL))
  //               + max(b[i+1]-f[i+1],0LL);
  // }
  return res;
}

int main(){
  scanf("%d%d",&H,&W);
  vll dp(H+1,vl(W)),p(H,vl(W)),f(H,vl(W));
  rep(i,H) rep(j,W) scanf("%lld",&p[i][j]);
  rep(i,H) rep(j,W) scanf("%lld",&f[i][j]);
  REP(j,1,W) dp[0][j] = -LINF;
  dp[0][0] = 0LL;
  rep(i,H){
    auto d1 = move(update(dp[i],p[i],f[i]));
    reverse(ALL(dp[i]));
    reverse(ALL(p[i]));
    reverse(ALL(f[i]));
    auto d2 = move(update(dp[i],p[i],f[i]));
    reverse(ALL(d2));
    rep(j,W) dp[i+1][j] = -LINF;
    rep(j,W) dp[i+1][j] = max(d1[j],d2[j]);
  }
  rep(j,W) cout << dp[H][j] << endl;
  return 0;
}