題面：給出長度為n的數列，然后算出其區間和乘區間最小數所能得到的最大值，并且輸出區間
樣例輸入：
6
3 1 6 4 5 2
樣例輸出：
60
3 5
原題鏈接：https://vjudge.net/problem/UVA-1619
分析：
這里有兩種演算法，一種是O(nlogn)的，用st表+遞回，另一種是O(n)的，用單調堆疊，
容易知道對于數列中的每一個數作為相應區間最小值時，雖然這個相應區間不一定唯一的，但是這個最大區間和一定是唯一的，
舉個栗子：
對于數列{0, 0, 0, 0, 0}來說，我們不管是選擇哪一個元素作為區間最小值，其相應的答案區間都有多種可能，但最大區間和肯定都是0（你選取第一個0作為區間最小值， 那區間可以是[1, 1]，[1, 2]，[1, 3]等等，但是區間和最大值肯定都是0），
我們看原題的話就會發現原題說明是關于這個區間的輸出，我們輸出其中合法的任何一個就行了，
但是！但是！其實這是在坑你！表面上是spj，實際上并不是spj！對于每一個給定的資料，其輸出的區間也必須也是要跟他給的一毛一樣才行orz，具體的潛規則我也不是很清楚，反正用單調堆疊才能AC，不過本著真理至上的原則，還是兩個演算法都講一遍，
================
st表+遞回解法
這種做法是列舉區間，然后通過st表O(1)找出區間的最小值，配合前輟和能直接計算出一個可能答案，
那怎么列舉區間呢？
先說下，st表保存的應該是區間最小值的下標 ，
比較直觀的一點就是當我們選取這個數列的最小值作為區間的最小值的時候，這個區間[1, n]肯定是合法的，設這個最小值的位置為k，那么我們可以知道[1, k-1]， [k+1, n]這兩個區間是另外兩個該被列舉的區間，然后找出這兩個區間最小值的位置，又能將區間再次分割，，，每次所劃分的區間所對應的區間最小值所在的位置都是不一樣的，通過這個遞回程序，如此一來，我們就得到了一個O(n)列舉區間的方法，之所以這個演算法是O(nlogn)只是因為建st表要O(nlogn)罷了，其他操作要么O(n)要么O(1)的，只可惜實際上這道題不是spj，這種方法跟單調堆疊的做法雖然都是對的，但是所得區間不一定一樣，不然資料水點的話說不定也能過(x)，
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 6 const int N = 1e5 + 10; 7 int Logn[N]; 8 long long a[N]; 9 long long sum[N]; //前輟和 10 int st[N][30]; //記錄區間[l, r]中最小元素下標的st表 11 long long ans; //最終答案 12 int L, R; //最終答案區間 13 14 void pre() { 15 Logn[1] = 0; 16 for (int i = 2; i < N; i++) 17 Logn[i] = Logn[i / 2] + 1; 18 } 19 20 void Build_st(int n) //建立st表 21 { 22 int logn = Logn[n]; 23 for(int j=1; j<=logn ;j++) 24 for (int i = 1; i + (1 << j) - 1 <= n; i++) { 25 if (a[st[i][j - 1]] < a[st[i + (1 << (j - 1))][j - 1]]) 26 st[i][j] = st[i][j - 1]; 27 else st[i][j] = st[i + (1 << (j - 1))][j - 1]; 28 } 29 } 30 31 int Query(int l, int r) 32 { 33 int s = Logn[r - l + 1]; 34 35 if (a[st[l][s]] < a[st[r + 1 - (1 << s)][s]]) return st[l][s]; 36 else return st[r + 1 - (1 << s)][s]; 37 } 38 39 void solve(int l, int r) //遞回處理 40 { 41 if (l > r) return; 42 43 int m = Query(l, r); 44 long long res = (sum[r] - sum[l-1]) * a[m]; 45 if (res > ans) { 46 ans = res; 47 L = l; 48 R = r; 49 } 50 51 solve(l, m - 1); 52 solve(m + 1, r); 53 } 54 55 int main() 56 { 57 //freopen("data.txt", "r", stdin); 58 //freopen("WA.txt", "w", stdout); 59 ios::sync_with_stdio(false); 60 pre(); 61 int n; 62 while (cin >> n) { 63 ans = -1; 64 65 for (int i = 1; i <= n; i++) { 66 cin >> a[i]; 67 sum[i] = a[i] + sum[i - 1]; 68 st[i][0] = i; 69 } 70 71 Build_st(n); 72 solve(1, n); 73 cout << ans << endl; 74 cout << L << " " << R << endl; 75 cout << endl; 76 } 77 78 return 0; 79 }
================
單調堆疊解法
單調堆疊的話做法就很單純了，用陣列l[i], r[i]分別保存元素a[i]作為區間最小值時所能延伸到的最左端跟最右端，用單調堆疊掃描兩次這兩個陣列的值就能全部出來了，實際寫代碼的時候博主寫慣了不小心寫成了單調佇列，不過操作都一樣的，，，
1 #include<iostream> 2 #include<algorithm> 3 #include<queue> 4 using namespace std; 5 6 typedef long long ll; 7 const int Maxn = 1e5 + 10; 8 ll a[Maxn]; 9 ll l[Maxn]; 10 ll r[Maxn]; 11 ll sum[Maxn]; 12 13 int main() 14 { 15 int n; 16 bool first = true; 17 while (cin >> n) { 18 if (first) first = false; 19 else cout << endl; 20 21 for (int i = 1; i <= n; i++) { 22 cin >> a[i]; 23 sum[i] = sum[i - 1] + a[i]; 24 } 25 26 deque <ll > rq, lq; 27 for (int i = 1; i <= n; i++) { 28 while (!rq.empty() && a[rq.back()] > a[i]) { 29 r[rq.back()] = i - 1; 30 rq.pop_back(); 31 } 32 33 rq.push_back(i); 34 } 35 while (!rq.empty()) { 36 r[rq.front()] = n; 37 rq.pop_front(); 38 } 39 40 for (int i = n; i >= 1; i--) { 41 while (!lq.empty() && a[lq.back()] > a[i]) { 42 l[lq.back()] = i + 1; 43 lq.pop_back(); 44 } 45 46 lq.push_back(i); 47 } 48 while (!lq.empty()) { 49 l[lq.front()] = 1; 50 lq.pop_front(); 51 } 52 53 ll ans = 0; 54 ll ans_l = 1, ans_r = 1; 55 56 for(int i=1; i<=n ;i++) 57 if ((sum[r[i]] - sum[l[i] - 1]) * a[i] > ans) { 58 ans = (sum[r[i]] - sum[l[i] - 1]) * a[i]; 59 ans_l = l[i]; 60 ans_r = r[i]; 61 } 62 63 cout << ans << endl; 64 cout << ans_l << " " << ans_r << endl; 65 } 66 67 return 0; 68 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/96520.html
標籤：其他