http://acm.hdu.edu.cn/showproblem.php?pid=4374

去年多校的题 今年才做 不知道这一年都干嘛去了。。

DP的思路很好想 dp[i][j] = max(dp[i-1][g]+sum[i][j]-sum[i][g-1],dp[i][j]) abs(g-j)<=t  不过复杂度是相当高的 所以呢 就出现了个单调队列 把它优化下

所谓的单调队列其实也就是一队列 始终保持着队头是最大的 若满足不了距离的条件 队头+1 队尾始终保持更新 让满足的了距离而且比队里的更大的元素进来

。。因为一初始化错了 　WA了十多次啊 注意：有负数 

1 #include 
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 #define N 105 8 #define M 10005 9 #define LL __int6410 int a[N][M],que[M];11 int dp[N][M];12 int s1[N][M],s2[N][M];13 int main()14 {15     int i,j,n,m,x,t,str,end;16     while(cin>>n>>m>>x>>t)17     {18         memset(dp,128,sizeof(dp));19         memset(s1,0,sizeof(s1));20         memset(s2,0,sizeof(s2));21         for(i = 1; i <= n; i++)22             for(j = 1; j <= m ; j++)23             {24                 scanf("%d",&a[i][j]);25                 s1[i][j] = s1[i][j-1]+a[i][j];26             }27         for(i = 1 ; i <= n ;i++)28             for(j = m ; j >= 1; j--)29             s2[i][j] = s2[i][j+1]+a[i][j];30         for(i = x ; i>=1&&i>=x-t ; i--)31         dp[1][i] = s1[1][x]-s1[1][i-1];32         for(i = x ; i <= m&&i<=x+t ; i++)33         dp[1][i] = s2[1][x]-s2[1][i+1];34         for(i = 2; i <= n ; i++)35         {36             str = 0;end=0;37             for(j = 1;j <= m ; j++)38             {39                 while(str
           
            dp[i-1][que[end-1]]-s1[i][que[end-1]-1])40 end--;41 que[end++] = j;42 dp[i][j] = max(dp[i][j],dp[i-1][que[str]]-s1[i][que[str]-1]+s1[i][j]);43 if(j-que[str]>=t)44 str++;45 }46 str = 0;end=0;47 for(j = m ; j >= 1; j--)48 {49 while(str
            
             dp[i-1][que[end-1]]-s2[i][que[end-1]+1])50 end--;51 que[end++] = j;52 dp[i][j] = max(dp[i][j],dp[i-1][que[str]]-s2[i][que[str]+1]+s2[i][j]);53 if(que[str]-j>=t)54 str++;55 }56 }57 int maxz=dp[n][1];58 for(i = 1; i <= m ; i++)59 maxz = max(maxz,dp[n][i]);60 cout<
             
              <