程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 5280 Senior&#39;s Array 最大區間和

HDU 5280 Senior&#39;s Array 最大區間和

編輯：C++入門知識

HDU 5280 Senior's Array 最大區間和

題意：給定n個數，要求必須將其中某個數改為P，求改動後最大的區間和可以為多少。

水題。枚舉每個區間，如果該區間不修改（即修改該區間以外的數），則就為該區間和，若該區間要修改，因為必須修改，所以肯定是把最小的數修改為P能保證該區間最後和最大，所以比較兩種方案的較大者。對於每個區間取出的較大者，再取總共的最大者即可。注意一個trick，枚舉到整個區間的時候，是必須要修改一個數的，所以這個最大的這個區間只有一種方案。先預處理1~i的區間和，維護每個區間的最小值和區間和。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
using namespace std;

const int MAX = 1005;
const int INF = 1e9;

int n;
__int64 P, a[MAX];
__int64 sum[MAX], smallest[MAX][MAX];

void input()
{
    scanf(%d%I64d, &n, &P);
    for(int i = 1; i <= n; i++)
        scanf(%I64d, &a[i]);
}

void solve()
{
    smallest[0][0] = INF;
    sum[0] = 0;
    __int64 ans = P;
    for(int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + a[i];
    for(int i = 1; i <= n; i++)
    {
        smallest[i][i] = a[i];
        ans = max(ans, a[i]);
        for(int j = i + 1; j <= n; j++)
        {
            smallest[i][j] = min(smallest[i][j - 1], a[j]);
            ans = max(ans, sum[j] - sum[i - 1] - smallest[i][j] + P);
            if(i != 1 || j != n)
                ans = max(ans, sum[j] - sum[i - 1]);
        }
    }
    printf(%I64d
, ans);
}

int main()
{
    int T;
    scanf(%d, &T);
    while(T--)
    {
        input();
        solve();
    }
    return 0;
}