程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 5280 Senior's Array 最大區間和

HDU 5280 Senior's Array 最大區間和

編輯:關於C++

題意:給定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;
}

 

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved