AOJ1306 Balloon Collecting

Balloon Collecting

"Balloons should be captured efficiently", the game designer says. He is designing an oldfashioned game with two dimensional graphics. In the game, balloons fall onto the ground one after another, and the player manipulates a robot vehicle on the ground to capture the balloons.

動的計画法．

として， の時に風船を取りに行って間に合うならば に遷移可能， 今ある風船を家に置きに行って，次の風船を取りに言って間に合うならば に遷移可能．
間に合うかどうかは，そのまま次のを取る，家に置きに行って風船を次の風船を取るが， より小さければ良い．
家に帰る，と次の風船を取りに行くを別々に考えていてどういう遷移か分からずめちゃくちゃ時間を溶かした．こういう考え方がすぐに出来るようになりたい．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int dp[50][4];

int main() {
  int n;
  while(cin >> n && n) {

      vector<int> p(n + 1), t(n + 1);
      rep(i, n) cin >> p[i + 1] >> t[i + 1];

      rep(i, 50) rep(j, 4) dp[i][j] = INF;

      int id = -1;
      dp[0][0] = 0;
      rep(i, n) {
          int d = abs(p[i+1] - p[i]);
          bool flag = true;

          rep(j, 4) {
              if(dp[i][j] == INF) continue;

              if(j < 3 && d * (j + 1) <= t[i+1] - t[i]) {
                  flag = false;
                  dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + d);
              }

              if(p[i] * (j + 1) + p[i+1] <= t[i+1] - t[i]) {
                  flag = false;
                  dp[i+1][1] = min(dp[i+1][1], dp[i][j] + p[i] + p[i+1]);
              }
          }

          if(flag) {
              id = i+1;
              break;
          }
      }

      if(id != -1) cout << "NG " << id << endl;
      else {
          int ans = INF;
          rep(j, 4) {
              ans = min(ans, dp[n][j] + p[n]);
          }
          cout << "OK " << ans << endl;
      }
  }

  return 0;
}
Mar 23rd, 2016
300, aoj-icpc, 動的計画法