1157:LITTLE SHOP OF FLOWERS

問題文
http://poj.org/problem?id=1157

訳
http://wikiwiki.jp/pku/?1157%20LITTLE%20SHOP%20OF%20FLOWERS

メモ化再帰した。

#include<iostream>
#include<algorithm>
#define INF (1<<29)

using namespace std;

int h,w,v[102][102],memo[102][102];

int rec(int a,int b){

  if(a==h)return 0;
  if(b==w)return -INF;
  if(memo[a][b]<INF)return memo[a][b];

  int res=-INF;
  for(int i=b+1;i<=w;i++)
    res=max(res,rec(a+1,i));

  return memo[a][b]=res+v[a][b];
}

int main(void){

  cin >> h >> w;
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)cin >> v[i][j];

  fill(memo[0],memo[102],INF);

  int ans=-INF;
  for(int i=0;i<w;i++)ans=max(ans,rec(0,i));

  cout << ans << endl;

  return 0;
}