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; } }