Feel Good

---

題目大意就是求一段區(qū)間[l,r]，然后求這段區(qū)間的和乘上這段區(qū)間上的最小值的最大值。在3 1 6 4 5 2 中，[3,5]的最小值為4，和為15，乘積40為所有情況的最大值。

我的思路是對于每個數(shù)求一個區(qū)間，該數(shù)是這個區(qū)間的最小值，則問題轉(zhuǎn)化為求以該數(shù)為最小值的區(qū)間最大能延展多少（向左和向右）。

#include<cstdio> #include<cstring> const int maxn = 100005; typedef long long ll; ll arr[maxn]; ll left[maxn]; ll right[maxn]; ll sum[maxn]; int main() {int n;scanf("%d", &n);arr[0] = -1;arr[n + 1] = -1;for(int i = 1; i <= n; i ++){scanf("%lld", &arr[i]);}for(int i = 1; i <= n; i ++){sum[i] = sum[i - 1] + arr[i];}for(int i = 1; i <= n; i++){for(int j = i - 1; j >=0;){if(arr[i] > arr[j]){left[i] = j + 1;break;}else{j = left[j] - 1;}}}for(int i = n; i >= 1; i --){for(int j = i + 1; j <= n + 1; ){if(arr[i] > arr[j]){right[i] = j - 1;break;}else{j = right[j] + 1;//if(i == 2)printf("%d\n",right[j]);}}}ll maxans = 0;ll maxleft = 1;ll maxright = 1;for(int i = 1; i <= n; i ++){ll tmp = (sum[right[i]] - sum[left[i] - 1]) * arr[i];if(tmp > maxans){maxans = tmp;maxleft = left[i];maxright = right[i];}}printf("%lld \n", maxans);printf("%lld %lld \n", maxleft, maxright);return 0; }

總結(jié)

以上是生活随笔為你收集整理的TOJ2333 Feel Good的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。