Codeforces 846 C Four Segments 前缀和暴力枚举-白红宇

Codeforces 846 C Four Segments 前缀和暴力枚举

阅读量：5905 次

发布时间：2019-06-19

本文共 1605 字，大约阅读时间需要 5 分钟。

　　题目链接： http://codeforces.com/contest/846/problem/C

　　题目描述：在一串数中找到三个坐标delim0, delim1, delim2, 使得 the value of res = sum(0, delim0) - sum(delim0, delim1) + sum(delim1, delim2) - sum(delim2, n) is maximal.

　　解题思路：暴力枚举delim0, delim2 , 在固定delim0 枚举delim2的过程中找到最优的delim1, 证明：初始化delim1是delim0, 由于在向右移动delim2的过程中，我们要求的

　　　　　　　　是max{ (delim1,delim2) - (delim0, delim1) } ，我们保存最大值k，然后在向后更新delim2的时候，如果前缀和s[delim2] < k 的时候，就说明此时的sum(delim1, delim2)

　　　　　　　　是负数了，这个时候我们就应该让delime1 = delim2 了，这样才可以让sum(delim1, delim2) 为 0， delim1 为更小的数了，所以就是max(sum(delim1,delim2)-sum(d0,d1))

　　代码：

#include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               using namespace std;typedef long long ll;int n;const int maxn = 5e3 + 10;const ll INF = 1e18;ll a[maxn];ll sum[maxn];ll s( int i, int j ) { return sum[j-1] - sum[i-1];}int main() { scanf( "%d", &n ); for( int i = 1; i <= n; i++ ) { scanf( "%lld", a+i ); } sum[0] = 0; for( int i = 1; i <= n; i++ ) { sum[i] = sum[i-1] + a[i]; } ll ans = -INF; int a, b, c; a = b = c = 0; for( int i = 0; i <= n; i++ ) { int t = i; ll temp = sum[i]; for( int j = i; j <= n; j++ ) { if( sum[j] < temp ) { temp = sum[j]; t = j; } ll res = s(1,i+1) - s(i+1,t+1) + s(t+1,j+1) - s(j+1,n+1); if( res >= ans ) { a = i, b = t, c = j; ans = res; } } } printf( "%d %d %d\n", a, b, c ); return 0;}

View Code

　　思考：这道题自己没有做出来，看了别人的代码也想了一段时间，所以当我们暴力枚举的时候，一定要看看其中的一维会不会是由另一维推出来的，这样就可以达到降低时间复杂度的目的

转载于:https://www.cnblogs.com/FriskyPuppy/p/7620141.html

你可能感兴趣的文章