POJ 3413 - RPG

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

概要

経験値 D から始めて N 個のクエストをこなす．

i 番目のクエストに成功すると S[i] の経験値が得られる． i 番目のクエストに成功する確率は，そのときの経験値を XP とすると

• 0 if XP < a[i]
• (XP - a[i])/(b[i] - a[i]) if a[i] <= XP < b[i]
• 1 if XP >= b[i]

で与えられる．

適切な順にクエストを進め，すべてのクエストに成功する最大の確率と，そのときの順番を答える．

制約

• 1 <= N <= 10
• 0 <= D, a[i], b[i], S[i] <= 1000
• a[i] < b[i]

解法

最大でもクエストは10個しかないので全通り試すだけ．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 static const double EPS = 1e-6;
 5 
 6 struct quest { int a, b, s; };
 7 
 8 double simulate(const quest *v, int N, int XP)
 9 {
10   double p = 1.0;
11   for (int i = 0; i < N; i++) {
12     if (XP < v[i].a) {
13       return 0.0;
14     } else if (v[i].a <= XP && XP < v[i].b) {
15       p *= double(XP - v[i].a)/double(v[i].b - v[i].a);
16       XP += v[i].s;
17     } else {
18       XP += v[i].s;
19     }
20   }
21   return p;
22 }
23 
24 int main()
25 {
26   int N, D;
27   scanf("%d %d", &N, &D);
28   quest v[10];
29   int a[10];
30   for (int i = 0; i < N; i++) {
31     a[i] = i;
32     scanf("%d %d %d", &v[i].a, &v[i].b, &v[i].s);
33   }
34 
35   quest w[10];
36   double ans = -1;
37   int perm[10];
38   do {
39     for (int i = 0; i < N; i++) {
40       w[i] = v[a[i]];
41     }
42     const double x = simulate(w, N, D);
43     if (x+EPS > ans) {
44       ans = x;
45       copy(a, a+N, perm);
46     }
47   } while (next_permutation(a, a+N));
48 
49   printf("%.3f\n", ans);
50   for (int i = 0; i < N; i++) {
51     if (i != 0) {
52       putchar(' ');
53     }
54     printf("%d", perm[i]+1);
55   }
56   putchar('\n');
57   return 0;
58 }