POJ 2796 - Feel Good

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

概要

n 個の emotional value の数列が与えられる． ある区間の emotional value は，その区間の emotional value の和と，その区間の最小値の積とする．

emotional value が最大になる区間と，そのときの値を答える． 最大になる区間が複数ある場合，どれを出力しても構わない．

制約

解法

emotional value は，区間の最小値が同じなら，できるだけ区間は広くしたほうがいいという点に注目する．

まず累積和と RMQ を作っておく． RMQ の実装は Sparce Table algorithm を使った． これは構築に O(N log N)，クエリに O(1) という実装．

最初は [1, n] という区間から始めて，区間の emotional value を累積和から計算して最大値を更新する． そして，区間の最小値のインデックスで区間を左右に分け，再帰的に最大値を更新していく．

例えばサンプルに対しては

というように処理が進む．

はじめ，この処理を再帰関数で実装していたので，昇順・降順な数列について n 段スタックを消費して Runtime Error になっていた． そこで queue を使ったループに書き直したら 1907MS で通った． 何ページか status を眺めてみるとかなり遅いほうで，無理矢理通した感がある (そしてコードも長い…)．

 1 #include <cstdio>
 2 #include <utility>
 3 #include <queue>
 4 using namespace std;
 5 static const int M = 100000;
 6 static const int K = 25;
 7 
 8 int log2(int n)
 9 {
10   int c = 0;
11   for (int x = 1; x <= n; x <<= 1) {
12     ++c;
13   }
14   return c-1;
15 }
16 
17 struct RMQ
18 {
19   const int *v;
20   int (*m)[K];
21   int N;
22   RMQ(const int *v_, int N_, int (*mem)[K])
23     : v(v_), m(mem), N(N_)
24   {
25     for (int i = 0; i < N; i++) {
26       m[i][0] = i;
27     }
28     for (int j = 1; (1<<j) <= N; j++) {
29       for (int i = 0; i + (1<<j) - 1 < N; i++) {
30         if (v[m[i][j-1]] < v[m[i+(1<<(j-1))][j-1]]) {
31           m[i][j] = m[i][j-1];
32         } else {
33           m[i][j] = m[i + (1<<(j-1))][j-1];
34         }
35       }
36     }
37   }
38 
39   int query(int i, int j) const
40   {
41     const int k = log2(j - i + 1);
42     if (v[m[i][k]] <= v[m[j-(1<<k)+1][k]]) {
43       return m[i][k];
44     } else {
45       return m[j-(1<<k)+1][k];
46     }
47   }
48 };
49 
50 pair<long long, pair<int,int> > solve(const int *v, const RMQ& m, const long long *sums, int beg, int end)
51 {
52   queue<pair<int,int> > q;
53   pair<long long, pair<int,int> > ans = make_pair((sums[end+1] - sums[beg]) * v[m.query(beg, end)], make_pair(beg, end));
54   q.push(make_pair(beg, end));
55   while (!q.empty()) {
56     const int b = q.front().first;
57     const int e = q.front().second;
58     const int i = m.query(b, e);
59     const long long x = (sums[e+1] - sums[b]) * v[i];
60     q.pop();
61     if (x > ans.first) {
62       ans.first = x;
63       ans.second = make_pair(b, e);
64     }
65     if (b <= i-1) {
66       q.push(make_pair(b, i-1));
67     }
68     if (i+1 <= e) {
69       q.push(make_pair(i+1, e));
70     }
71   }
72   return ans;
73 }
74 
75 int main()
76 {
77   int N;
78   scanf("%d", &N);
79   static int v[M];
80   for (int i = 0; i < N; i++) {
81     scanf("%d", &v[i]);
82   }
83 
84   static int mem[M][K];
85   RMQ rmq(v, N, mem);
86 
87   static long long sums[M+1];
88   for (int i = 0; i < N; i++) {
89     sums[i+1] = sums[i] + v[i];
90   }
91 
92   const pair<long long, pair<int,int> > ans = solve(v, rmq, sums, 0, N-1);
93   printf("%lld\n", ans.first);
94   printf("%d %d\n", ans.second.first+1, ans.second.second+1);
95   return 0;
96 }
poj/2796.cc