4212:Candy

問題文
https://icpcarchive.ecs.baylor.edu/external/42/4212.pdf

n*mのグリッドが与えられる。マスの数字はそのマスにあるキャンディーの個数だ。このグリッドのあるマスからそのマスにあるキャンディーを全てとるとき、図のようにそのマスの左右のマスと上下の列にあるキャンディーがすべて消えてしまう。取れるキャンディーの最大値を求めよ。

まず全ての行について、その行で取れるキャンディーの最大値を計算する。
dp[ マスの番号 ] := そのマスまでで取れるキャンディーの最大値
dp[ i ] = max( dp[ i - 1 ], dp[ i - 2 ] + w[ i ] )

それができたら、今度は各行での最大値に対して同じことをする。

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main(void){
 
  int n,m;
  while(cin >> n >> m,n|m){
    int g[n+2],v[m+2];
    fill(g,g+n+2,0);
    
    for(int i=1;i<=n;i++){
      fill(v,v+m+2,0);
      for(int j=1;j<=m;j++)cin >> v[j];
      vector<int> dp(m+2);
      dp[0]=0,dp[1]=v[1];
      for(int j=2;j<=m;j++)
	dp[j] = max(dp[j-1], dp[j-2]+v[j]);
      
      g[i]=dp[m];
    }
    
    vector<int> dp(n+2);
    dp[0]=0,dp[1]=g[1];
    for(int j=2;j<=n;j++)
      dp[j] = max(dp[j-1], dp[j-2]+g[j]);
    
    cout << dp[n] << endl;
  }
  return 0;
}