HDU 3415 Max Sum of Max-K-sub-sequence ( 单调队列 )

题目链接~~>

做题感悟：看这题是就很有单调队列的赶脚，但是还是花费了很长时间做出来。

解题思路：

                 动态方程很好推： dp [ i ] = min { sum[ i ] - sum[ j - 1] }   i - j  + 1 <= k ,我们可以变一下型 ，dp [ i ] = sum[ i ] - min { sum[ j - 1 ] } ，这样 sum[ j - 1 ] 就可以用单调队列来维护了。因为是环形的，可以展开成为两倍。

代码：

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<cmath>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<cstring>
     
    
   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<stack>
     
    
   

    

     

    
    

     

      #include<bitset>
     
    
   

    

     

    
    

     

      #include<ctime>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<cctype>
     
    
   

    

     

    
    

     

      #include<iomanip>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std  ;
     
    
   

    

     

    
    

     

      #define INT long long int
     
    
   

    

     

    
    

     

      #define L(x) (x * 2)
     
    
   

    

     

    
    

     

      #define R(x) (x * 2 + 1)
     
    
   

    

     

    
    

     

      const int INF = 0x3f3f3f3f ;
     
    
   

    

     

    
    

     

      const double esp = 0.0000000001 ;
     
    
   

    

     

    
    

     

      const double PI = acos(-1.0) ;
     
    
   

    

     

    
    

     

      const int mod = 1000000007 ;
     
    
   

    

     

    
    

     

      const int MY = (1<<5) + 5 ;
     
    
   

    

     

    
    

     

      const int MX = 200000 + 5 ;
     
    
   

    

     

    
    

     

      const int S = 20 ;
     
    
   

    

     

    
    

     

      int n ,k ,St ,End ,ans ,m ;
     
    
   

    

     

    
    

     

      int g[MX] ,sum[MX] ,deq[MX] ,deqv[MX] ;
     
    
   

    

     

    
    

     

      void input()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
   scanf("%d%d" ,&n ,&k) ;
     
    
   

    

     

    
    

     

         sum[0] = 0 ;
     
    
   

    

     

    
    

     
   for(int i = 1 ;i <= n ; ++i)
     
    
   

    

     

    
    

     

         {
     
    
   

    

     

    
    

     
 scanf("%d" ,&g[i]) ;
     
    
   

    

     

    
    

     

       g[i+n] = g[i] ;
     
    
   

    

     

    
    

     

         }
     
    
   

    

     

    
    

     

         m = n ;
     
    
   

    

     

    
    

     

         n = n*2 ;
     
    
   

    

     

    
    

     
   for(int i = 1 ;i <= n ; ++i)
     
    
   

    

     

    
    

     

       sum[i] = sum[i-1] + g[i] ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void DP()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int front = 0 ,end = 0 ,temp ,a1 ,a2 ;
     
    
   

    

     

    
    

     

       St = INF ; ans = -INF ; End = 0 ;
     
    
   

    

     

    
    

     

       ans = -INF ;
     
    
   

    

     

    
    

     
 for(int i = 1 ;i <= n ; ++i)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 while(front < end && deqv[end-1] > sum[i-1])  // 去除大于等于此元素的值
     
    
   

    

     

    
    

     

       end-- ;
     
    
   

    

     

    
    

     

       deq[end] = i-1 ;
     
    
   

    

     

    
    

     

       deqv[end++] = sum[i-1] ;
     
    
   

    

     

    
    

     

       temp = sum[i] - deqv[front] ;
     
    
   

    

     

    
    

     
 if(temp > ans)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       ans = temp ;
     
    
   

    

     

    
    

     

       St = deq[front] + 1 ;
     
    
   

    

     

    
    

     

       End = i ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 while(front < end && deq[front] <= i-k)  // 去除冗余元素
     
    
   

    

     

    
    

     

       front++ ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 //freopen("input.txt" ,"r" ,stdin) ;
     
    
   

    

     

    
    

     
 int Tx ;
     
    
   

    

     

    
    

     
 scanf("%d" ,&Tx) ;
     
    
   

    

     

    
    

     
 while(Tx--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       input() ;
     
    
   

    

     

    
    

     

       DP() ;
     
    
   

    

     

    
    

     
 if(St > m) St -= m ;
     
    
   

    

     

    
    

     
 if(End > m)  End -= m ;
     
    
   

    

     

    
    

     
 printf("%d %d %d\n" ,ans ,St ,End) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/41012227