HDU 5280 Senior's Array 最大区间和 - c++编程基础

TOP

HDU 5280 Senior's Array 最大区间和

2015-11-21 00:57:17 来源: 作者: 【大中小】浏览:2次

题意：给定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; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDU 5281 Senior's Gun 杀怪	下一篇：C++ 递归和非递归实现链表逆序

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: