live archive 5024 - Falling Gift Game

問題概要

1次元グリッドを考える。
ある一方向にしか進めない。
距離1進むためには、1秒かかる。
それぞれの場所にギフトが降ってくる。
価値と降ってくる時間が与えられる。
得られる最大の価値を求めよ。
スタート地点はいつも0の地点。

解法

DP
状態は今の場所と時間

ソース

#include<iostream>

#define REP(i, b, n) for(int i = b; i<(int)n; i++)
#define rep(i, n) REP(i, 0, n)

using namespace std;

const int N = 500;
const int G = N * 2 +1;

int main(){
  int n;
  while(cin >> n){
    if(n == 0)break;
    int t[N], p[N];
    rep(i, n)cin >> t[i] >> p[i];
    int dp[G][N];
    rep(i, G){
      rep(j, N){
	dp[i][j] = 0;
      }
    }
    rep(i, G-1){
      rep(j, min(n, i+1)){
	if(i == t[j]){
	  dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + p[j]);
	  dp[i+1][j] = max(dp[i+1][j], dp[i][j] + p[j]);
	}
	else {
	  dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]);
	  dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
	}
      }
    }
    cout << dp[G-1][n] << endl;
  }
}