A DNA sequence consists of four letters, A, C, G, and T. The GC-ratio of a DNA sequence is the

number of Cs and Gs of the sequence divided by the length of the sequence. GC-ratio is important

in gene nding because DNA sequences with relatively high GC-ratios might be good candidates for

the starting parts of genes. Given a very long DNA sequence, researchers are usually interested in

locating a subsequence whose GC-ratio is maximum over all subsequences of the sequence. Since short

subsequences with high GC-ratios are sometimes meaningless in gene nding, a length lower bound is

given to ensure that a long subsequence with high GC-ratio could be found. If, in a DNA sequence,

a 0 is assigned to every A and T and a 1 to every C and G, the DNA sequence is transformed into a

binary sequence of the same length. GC-ratios in the DNA sequence are now equivalent to averages in

the binary sequence.

题目大意:给出一个01序列，求长度至少为L的子序列，使得平均值最大

解题报告:

比较简单，但是花了许久时间，还是太渣.

开始以为是简单贪心，长度固定为L即可，发现这个单调性只有排序后才有QWQ,所以拍WA后改写斜率优化DP:我们要求的是\((sum[i]-sum[j])/(i-j+1)\)最大值，明显对应平面上的斜率，所以直接做就好，注意要把0加进去，调了很久

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define RG register#define il inline#define iter iterator#define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)<(b)?(a):(b))using namespace std;const int N=1e5+5;const double eps=1e-6;int a[N],n,m,sum[N],q[N];char s[N];int fy(int i,int j){ return sum[i]-sum[j];}int fx(int i,int j){ return i-j;}void work(){ scanf("%d%d",&n,&m); scanf("%s",s+1); for(int i=1;i<=n;i++){ a[i]=s[i]-'0',sum[i]=sum[i-1]+a[i]; if(m==1 && a[i]){ printf("%d %d\n",i,i); return ; } } if(m==1){puts("1 1");return ;} int l=1,r=0,j,k,L=0,R=m;int tot; for(int i=m;i<=n;i++){ while(r-l>=1){ j=q[r];k=q[r-1]; if(fy(i-m,j)*fx(i-m,k)<=fy(i-m,k)*fx(i-m,j))r--; else break; } q[++r]=i-m; while(r-l>=1){ j=q[l+1];k=q[l]; if(fy(i,j)*fx(i,k)>=fy(i,k)*fx(i,j))l++; else break; } tot=fy(i,q[l])*fx(R,L)-fy(R,L)*fx(i,q[l]); if(tot>0 || (tot==0 && i-q[l]
          
           >T; while(T--)work(); return 0;}