升级蓄水池

C++14 解法, 执行用时: 6ms, 内存消耗: 488KB, 提交时间: 2020-06-09

#include <iostream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
using namespace std;
     
vector<int> calLeft(int n, vector<int>& h) 
{
    vector<int> next;
    next.push_back(0);
    for (int i = 1; i < n; i++)
    {
        if (h[i] > h[next.back()])
            next.push_back(i);
    }
    return next;
}
     
vector<int> calRight(int n, vector<int>& h) 
{
    vector<int> next;
    next.push_back(n-1);
    for (int i = n - 2; i >= 0; i--)
    {
        if (h[i] > h[next.back()])
            next.push_back(i);
    }
    return next;
}
     
vector<int> calRemain(vector<int>& next, vector<int>& h) 
{
    int r = 0;
    vector<int> remain(next.size());
    for (int i = 1; i < remain.size(); i++) 
    {
        r = max(abs(next[i] - next[i - 1]) - 1, r);
        remain[i] = r;
    }
    return remain;
}
     
vector<int> calMaxV(vector<int>& next, int m, vector<int>& sum, vector<int>& h, vector<int>& zero) {
    vector<int> maxP(m+1);
    for (int i = 0; i < next.size()-1; i++)
    {
        zero[i] = maxP[0];
        int temp = maxP[0], temp1 = m > 1?maxP[1]:0;
        int rightI = i + 1;
        for (int j = 0; j <= m; j++) {
            maxP[j] = max(maxP[j], j > 0 ? maxP[j - 1] : 0);
            while (rightI < next.size() && h[next[i]] + j > h[next[rightI]])
                rightI++;
            int width = abs(next[min(rightI, (int)next.size()-1)] - next[i]) - 1;
            int height = min((h[next[i]] + j), h[next.back()]);
            int build = abs(sum[next[min(rightI, (int)next.size() - 1)] - (next[0] < next[1])] - sum[next[i] - (next[0] > next[1])]);
            int pre = rightI == next.size() ? temp1 : temp;
            int newP = width * height - build + pre;
            maxP[j] = max(newP, maxP[j]);
        }
    }
    zero[zero.size() - 1] = maxP[0];
    return maxP;
}
     
     
int main() 
{
    int n, m,s = 0, maxI = 0;
    cin >> n;
    vector<int> h(n), sum(n), rsum(n);
    for (int i = 0; i < n; i++) 
    {
        cin >> h[i];
        s += h[i];
        sum[i] = s;
        if (h[i] > h[maxI])
            maxI = i;
    }
    s = 0;
    for (int i = n - 1; i >= 0; i--) 
    {
        s += h[i];
        rsum[n - i - 1] = s;
    }
    cin >> m;
    //m++;
         
    vector<int> left = calLeft(n, h);
    vector<int> right = calRight(n, h);
    vector<int> leftZero(left.size()), rightZero(right.size());
    vector<int> reLeft = calRemain(left, h);
    vector<int> reRight = calRemain(right, h);
    vector<int> maxL = calMaxV(left, m, sum, h, leftZero);
    vector<int> maxR = calMaxV(right, m, sum, h, rightZero);
    int ans = 0;
    for (int i = 0; i <= m; i++) 
    {
        ans = max(ans, maxL[i] + maxR[m - i]) ;
    }
         
    if (right.back() != left.back())
        ans += (right.back() - left.back() - 1) * h[left.back()] - sum[right.back() - 1] + sum[left.back()];
     
    for (int i = 0; i < left.size(); i++) 
    {
        for (int j = 0; j < right.size() && right[j] > left[i]; j++) 
        {
            int width = right[j] - left[i]  - 1;
            int height = (h[right[j]] + h[left[i]] + m ) / 2;
            if (height <= h[left.back()])
                continue;
            int build = sum[right[j]-1] - sum[left[i]];
            int pre = (h[right[j]] + h[left[i]] + m) % 2 == 0 ? 0 : max(reRight[j], reLeft[i]);
            int newP = width * height - build + pre + leftZero[i] + rightZero[j];
            ans = max(newP, ans);
        }
    }
    cout << ans;
     
    return 0;
}

C++ 解法, 执行用时: 6ms, 内存消耗: 504KB, 提交时间: 2020-10-15

#include <iostream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
using namespace std;
       
vector<int> calLeft(int n, vector<int>& h)
{
    vector<int> next;
    next.push_back(0);
    for (int i = 1; i < n; i++)
    {
        if (h[i] > h[next.back()])
            next.push_back(i);
    }
    return next;
}
       
vector<int> calRight(int n, vector<int>& h)
{
    vector<int> next;
    next.push_back(n-1);
    for (int i = n - 2; i >= 0; i--)
    {
        if (h[i] > h[next.back()])
            next.push_back(i);
    }
    return next;
}
       
vector<int> calRemain(vector<int>& next, vector<int>& h)
{
    int r = 0;
    vector<int> remain(next.size());
    for (int i = 1; i < remain.size(); i++)
    {
        r = max(abs(next[i] - next[i - 1]) - 1, r);
        remain[i] = r;
    }
    return remain;
}
       
vector<int> calMaxV(vector<int>& next, int m, vector<int>& sum, vector<int>& h, vector<int>& zero) {
    vector<int> maxP(m+1);
    for (int i = 0; i < next.size()-1; i++)
    {
        zero[i] = maxP[0];
        int temp = maxP[0], temp1 = m > 1?maxP[1]:0;
        int rightI = i + 1;
        for (int j = 0; j <= m; j++) {
            maxP[j] = max(maxP[j], j > 0 ? maxP[j - 1] : 0);
            while (rightI < next.size() && h[next[i]] + j > h[next[rightI]])
                rightI++;
            int width = abs(next[min(rightI, (int)next.size()-1)] - next[i]) - 1;
            int height = min((h[next[i]] + j), h[next.back()]);
            int build = abs(sum[next[min(rightI, (int)next.size() - 1)] - (next[0] < next[1])] - sum[next[i] - (next[0] > next[1])]);
            int pre = rightI == next.size() ? temp1 : temp;
            int newP = width * height - build + pre;
            maxP[j] = max(newP, maxP[j]);
        }
    }
    zero[zero.size() - 1] = maxP[0];
    return maxP;
}
       
       
int main()
{
    int n, m,s = 0, maxI = 0;
    cin >> n;
    vector<int> h(n), sum(n), rsum(n);
    for (int i = 0; i < n; i++)
    {
        cin >> h[i];
        s += h[i];
        sum[i] = s;
        if (h[i] > h[maxI])
            maxI = i;
    }
    s = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        s += h[i];
        rsum[n - i - 1] = s;
    }
    cin >> m;
    //m++;
           
    vector<int> left = calLeft(n, h);
    vector<int> right = calRight(n, h);
    vector<int> leftZero(left.size()), rightZero(right.size());
    vector<int> reLeft = calRemain(left, h);
    vector<int> reRight = calRemain(right, h);
    vector<int> maxL = calMaxV(left, m, sum, h, leftZero);
    vector<int> maxR = calMaxV(right, m, sum, h, rightZero);
    int ans = 0;
    for (int i = 0; i <= m; i++)
    {
        ans = max(ans, maxL[i] + maxR[m - i]) ;
    }
           
    if (right.back() != left.back())
        ans += (right.back() - left.back() - 1) * h[left.back()] - sum[right.back() - 1] + sum[left.back()];
       
    for (int i = 0; i < left.size(); i++)
    {
        for (int j = 0; j < right.size() && right[j] > left[i]; j++)
        {
            int width = right[j] - left[i]  - 1;
            int height = (h[right[j]] + h[left[i]] + m ) / 2;
            if (height <= h[left.back()])
                continue;
            int build = sum[right[j]-1] - sum[left[i]];
            int pre = (h[right[j]] + h[left[i]] + m) % 2 == 0 ? 0 : max(reRight[j], reLeft[i]);
            int newP = width * height - build + pre + leftZero[i] + rightZero[j];
            ans = max(newP, ans);
        }
    }
    cout << ans;
       
    return 0;
}

详情