POJ 1297 - Supermarket

http://poj.org/problem?id=1297

概要

M 個の商品名が書かれた買い物のリストが与えられる． 通路に沿って N 個の商品が並んでおり，i 番目の商品名は K[i] で，値段は P[i]． その通路を一度だけ通って，リストの順番に従って商品を買う．

買い物の費用の合計の最小化したい． そのときの費用の合計を答える． ただし，リストにあるすべての商品を買えないときは「Impossible」と出力する．

制約

解法

dp[i][j] = リストのi番目までの商品を，j番目までで買ったときの最小値

として，

dp[i][j] = min(dp[i][j-1], dp[i-1][j-1] + price[j])  if product[j] == order[i]
 = dp[i-1][j-1]                              otherwise

と埋めていく DP．

 1 #include <cstdio>
 2 #include <utility>
 3 #include <algorithm>
 4 using namespace std;
 5 static const double INF = 100000 * 200;
 6 int M, N;
 7 int order[100];
 8 pair<int,double> shops[100000];
 9 
10 double solve()
11 {
12   static double dp[100000];
13   dp[0] = shops[0].first == order[0] ? shops[0].second : INF;
14   for (int j = 1; j < N; j++) {
15     if (shops[j].first == order[0]) {
16       dp[j] = min(dp[j-1], shops[j].second);
17     } else {
18       dp[j] = dp[j-1];
19     }
20   }
21 
22   static double dp_next[100000];
23   for (int i = 1; i < M; i ++) {
24     fill_n(dp_next, N, INF);
25     for (int j = i; j < N; j++) {
26       if (shops[j].first == order[i]) {
27         dp_next[j] = min(dp_next[j-1], dp[j-1] + shops[j].second);
28       } else {
29         dp_next[j] = dp_next[j-1];
30       }
31     }
32     copy(dp_next, dp_next + N, dp);
33   }
34 
35   return dp[N-1];
36 }
37 
38 int main()
39 {
40   while (scanf("%d %d", &M, &N) != EOF && M != 0) {
41     for (int i = 0; i < M; i++) {
42       scanf("%d", &order[i]);
43     }
44     for (int i = 0; i < N; i++) {
45       scanf("%d %lf", &shops[i].first, &shops[i].second);
46     }
47 
48     const double ans = solve();
49     if (ans >= INF) {
50       puts("Impossible");
51     } else {
52       printf("%.2f\n", ans);
53     }
54   }
55   return 0;
56 }
poj/1297.cc