hdu4374 单调队列优化dp

?

题意就不多说了，直接说思路吧；

对每一层的点都有两种方式到达（左边不超过T步 或右边不超过T步） 对这两种方式容易得出

?

?

因为每一层的sum是定的 所以 只要求满足条件的dp【i-1】【k】-sum[i][k-1]的最大值就行 这就用到单调队列来优化了

?

?

#include
  
   
#include
   
     #include
     
     using namespace std
     ; #define INF -0x3f3f3f3f 
      int sum
     [20100
     ],num
     [110
     ][20100
     ],id
     [20100
     ],dp
     [110
     ][20100
     ],map
     [10010
     ]; int max
     (int a
     ,int b
     ) { return a
     >b
     ?a
     :b
     ; } int main() { int n
     ,m
     ,i
     ,j
     ,x
     ,T
     ; while(~scanf
     ("%d%d%d%d"
     ,&n
     ,&m
     ,&x
     ,&T
     )) { for(i
     =1
     ;i
     <=n
     ;i
     ++) for(j
     =1
     ;j
     <=m
     ;j
     ++) { scanf
     ("%d"
     ,&num
     [i
     ][j
     ]); dp
     [i
     ][j
     ]=INF
     ; } dp
     [1
     ][x
     ]=num
     [1
     ][x
     ]; for(i
     =x
     -1
     ;i
     >=1
     &&x
     -i
     <=T
     ;i
     --) dp
     [1
     ][i
     ]=dp
     [1
     ][i
     +1
     ]+num
     [1
     ][i
     ]; for(i
     =x
     +1
     ;i
     <=m
     &&i
     -x
     <=T
     ;i
     ++) dp
     [1
     ][i
     ]=dp
     [1
     ][i
     -1
     ]+num
     [1
     ][i
     ]; int front
     ,top
     ; sum
     [0
     ]=0
     ; for(i
     =2
     ;i
     <=n
     ;i
     ++) { for(j
     =1
     ;j
     <=m
     ;j
     ++) sum
     [j
     ]=sum
     [j
     -1
     ]+num
     [i
     ][j
     ]; front
     =0
     ,top
     =0
     ; for(j
     =1
     ;j
     <=m
     ;j
     ++) { int tt
     =dp
     [i
     -1
     ][j
     ]-sum
     [j
     -1
     ]; while(front
     <top
     &&tt
     >map
     [top
     ]) top
     --; id
     [++top
     ]=j
     ; map
     [top
     ]=tt
     ; while(j
     -T
     >id
     [front
     +1
     ]&&front
     <top
     ) front
     ++; dp
     [i
     ][j
     ]=max
     (dp
     [i
     ][j
     ],map
     [front
     +1
     ]+sum
     [j
     ]); } front
     =0
     ,top
     =0
     ; sum
     [m
     +1
     ]=0
     ; for(j
     =m
     ;j
     >=1
     ;j
     --) sum
     [j
     ]=sum
     [j
     +1
     ]+num
     [i
     ][j
     ]; for(j
     =m
     ;j
     >=1
     ;j
     --) { int tt
     =dp
     [i
     -1
     ][j
     ]-sum
     [j
     +1
     ]; while(front
     <top
     &&tt
     >map
     [top
     ]) top
     --; id
     [++top
     ]=j
     ; map
     [top
     ]=tt
     ; while(front
     <top
     &&id
     [front
     +1
     ]>j
     +T
     ) front
     ++; dp
     [i
     ][j
     ]=max
     (dp
     [i
     ][j
     ],map
     [front
     +1
     ]+sum
     [j
     ]); } } int Max
     =INF
     ; for(i
     =1
     ;i
     <=m
     ;i
     ++) if(dp
     [n
     ][i
     ]>Max
     ) Max
     =dp
     [n
     ][i
     ]; printf
     ("%d\n"
     ,Max
     ); } return 0
     ; }
    
   
  

?