5790:Ball Stacking - tobiasの日記

問題文
https://icpcarchive.ecs.baylor.edu/external/57/5790.pdf

図のようにコストがついた玉がいくつか与えられる。ある玉を取り除くとそのコスト分だけ得点がもらえる。その玉の上に玉が無ければ取り除くことができる。得点を最大化せよ。

与えられる玉を回転させたように配列に入れる。Sample Input 1なら、

というように使う。この配列で、左から右に累積和をとる。そして、今みている玉を取らずに左に移動するのと、玉を取って下にいくのをメモ化再帰でやった。

#include<iostream>
#include<vector>
#include<algorithm>
#define INF (1LL<<62)
  
using namespace std;
  
typedef long long ll;
  
int g[1010][1010],n;
ll memo[1010][1010];
  
ll rec(int h,int w){
  if(h==n)return 0;
  if(memo[h][w]>-INF)return memo[h][w];
    
  ll res=0;
  if(w>0)res=max(res,rec(h,w-1));
  if(w<n-h)res=max(res,rec(h+1,w)+g[h][w]);
    
  return memo[h][w]=res;
}
  
int main(void){
    
  while(cin >> n,n){
    fill(g[0],g[1010],0);
      
    for(int i=0;i<n;i++)
      for(int j=0;j<=i;j++)cin >> g[j][i-j];
      
    for(int i=0;i<n;i++)
      for(int j=0;j<n-i;j++)g[i][j+1]+=g[i][j];
  
    fill(memo[0],memo[1010],-INF);
    cout << rec(0,n-1) << endl;
  }
  return 0;
}