acm.hdu.edu.cn/showproblem.php?pid=4374
题意：有n层，每层有m个part。在一层中你只能向着一个方向移动（左或者右），最多能移动T步，
经过每个部分是都能得到这个部分的分数。起始位置在x位置，从第一层到最顶层能得到最多的分数
题解：
dp + 单调队列 ；
对于 左边我们可以得到 dp[i][j] = max( dp[i - 1][k] + sum（k， j）) j - t <=k <= j；
我们的队列 要维护的 就是
dp[i - 1][k] + sum（k， j）
由于 sum （k ,j） 单调队列要维护的状态必须是和 现在的状态 无关（或着说是 以知的），但 sum(k,j) 用到了现在的状态；所以 我们要进行转换一下， sum(k,j) = sum (1,j) - sum (1,k - 1);
所以 原式变为
dp[i - 1][k] + sum (1,j) - sum (1,k - 1) = (dp[i - 1][k] - sum(1,k)) + sum (1,j)
而 dp[i -1][k] - sum(1,k - 1) 相对于 dp[i][j] 来说 是 以知的 所以
而 dp[i -1][k] - sum(1,k - 1) 相对于 dp[i][j] 来说 是 以知的 所以
dp[i -1][k] - sum(1,k - 1) 就是 我们 队列 要维护的状态
右边同理 可得
1 #include<stdio.h>
2 #include<iostream>
3 #include<algorithm>
4 #include<cstring>
5 #include<cmath>
6 #include<queue>
7 #include<set>
8 #include<list>
9 #include<map>
10 #define Min(a,b) a>b?b:a
11 #define Max(a,b) a>b?a:b
12 #define CL(a,num) memset(a,num,sizeof(a));
13 #define inf 99999999
14 #define maxn 10010
15 #define mod 100000007
16 #define eps 1e-6
17 #define ll long long
18 #define M 15520
19 using namespace std;
20 int n,m,x,t;
21 struct node
22 {
23 int x;
24 int w;
25 node(int xx,int yy): x(xx),w(yy){}
26 };
27 int f[110][maxn],sum[maxn] ,dp[110][maxn];
28 int main()
29 {
30 //freopen("data.txt","r",stdin);
31 int i ,j ;
32 while(scanf("%d%d%d%d",&n,&m,&x,&t)!=EOF)
33 {
34 list<node>que;
35 for(i = 0; i < n ;++i)
36 {
37 for(j = 1 ;j <= m; ++j)
38 scanf("%d",&f[i][j]);
39 }
40
41 for(i = 0; i <= n;++i)
42 {
43 for( j = 0; j <= m ;++j)
44 {
45 dp[i][j] = -inf ;
46 }
47 }
48 int cnt = f[0][x];
49 dp[0][x] = f[0][x] ;
50 for(i = 0,j = x - 1; i < t&& j >=1;i++,j--)//往左处理
51 { cnt += f[0][j];
52 dp[0][j] = cnt ;
53 }
54
55 cnt = f[0][x] ;
56 for(i = 0,j = x + 1; i < t && j <= m;i++,j++)// 往右处理
57 {
58 cnt += f[0][j] ;
59 dp[0][j] = cnt ;
60
61
62 }
63
64 for(i = 1; i < n;++i)
65 {
66 sum[0] = 0;
67 que.clear() ;// 注意要清空 我就 WA 一次
68 for(j = 1 ; j <= m ;++j)//左处理
69 {
70
71
72
73 sum[j] = sum[j - 1] + f[i][j] ;
74
75 while(!que.empty() && que.front().x < j - t) //距离 大于 t 了 要出队列
76 que.pop_front();
77
78 int tmp = dp[i - 1][j] - sum[j - 1] ;
79
80 while(!que.empty() && que.back().w <= tmp)
81 que.pop_back() ;
82
83 que.push_back(node(j,tmp));
84 if(!que.empty())
85 dp[i][j] = sum[j] + que.front().w ;
86
87 }
88
89
90
91
92
93 que.clear() ;
94 sum[m + 1] = 0;
95 for(j = m ; j >= 1 ;--j)// 右处理
96 {
97
98
99 sum[j] = sum[j + 1] + f[i][j] ;
100
101 while(!que.empty() && que.front().x - j > t)//距离 大于 t 了 要出队列
102 que.pop_front();
103
104 int tmp = dp[i - 1][j] - sum[j + 1] ;
105
106 while(!que.empty() && que.back().w <= tmp)
107 que.pop_back() ;
108
109 que.push_back(node(j,tmp));
110
111 if(!que.empty())
112 dp[i][j] = max(dp[i][j],sum[j] + que.front().w );
113
114 }
115
116
117 }
118
119 int ans = dp[n - 1][1];
120 for(i = 2;i <= m;++i)
121 {
122 ans = max(ans,dp[n - 1][i]);
123 }
124 printf("%d\n",ans);
125
126
127
128 }
129 }
2 #include<iostream>
3 #include<algorithm>
4 #include<cstring>
5 #include<cmath>
6 #include<queue>
7 #include<set>
8 #include<list>
9 #include<map>
10 #define Min(a,b) a>b?b:a
11 #define Max(a,b) a>b?a:b
12 #define CL(a,num) memset(a,num,sizeof(a));
13 #define inf 99999999
14 #define maxn 10010
15 #define mod 100000007
16 #define eps 1e-6
17 #define ll long long
18 #define M 15520
19 using namespace std;
20 int n,m,x,t;
21 struct node
22 {
23 int x;
24 int w;
25 node(int xx,int yy): x(xx),w(yy){}
26 };
27 int f[110][maxn],sum[maxn] ,dp[110][maxn];
28 int main()
29 {
30 //freopen("data.txt","r",stdin);
31 int i ,j ;
32 while(scanf("%d%d%d%d",&n,&m,&x,&t)!=EOF)
33 {
34 list<node>que;
35 for(i = 0; i < n ;++i)
36 {
37 for(j = 1 ;j <= m; ++j)
38 scanf("%d",&f[i][j]);
39 }
40
41 for(i = 0; i <= n;++i)
42 {
43 for( j = 0; j <= m ;++j)
44 {
45 dp[i][j] = -inf ;
46 }
47 }
48 int cnt = f[0][x];
49 dp[0][x] = f[0][x] ;
50 for(i = 0,j = x - 1; i < t&& j >=1;i++,j--)//往左处理
51 { cnt += f[0][j];
52 dp[0][j] = cnt ;
53 }
54
55 cnt = f[0][x] ;
56 for(i = 0,j = x + 1; i < t && j <= m;i++,j++)// 往右处理
57 {
58 cnt += f[0][j] ;
59 dp[0][j] = cnt ;
60
61
62 }
63
64 for(i = 1; i < n;++i)
65 {
66 sum[0] = 0;
67 que.clear() ;// 注意要清空 我就 WA 一次
68 for(j = 1 ; j <= m ;++j)//左处理
69 {
70
71
72
73 sum[j] = sum[j - 1] + f[i][j] ;
74
75 while(!que.empty() && que.front().x < j - t) //距离 大于 t 了 要出队列
76 que.pop_front();
77
78 int tmp = dp[i - 1][j] - sum[j - 1] ;
79
80 while(!que.empty() && que.back().w <= tmp)
81 que.pop_back() ;
82
83 que.push_back(node(j,tmp));
84 if(!que.empty())
85 dp[i][j] = sum[j] + que.front().w ;
86
87 }
88
89
90
91
92
93 que.clear() ;
94 sum[m + 1] = 0;
95 for(j = m ; j >= 1 ;--j)// 右处理
96 {
97
98
99 sum[j] = sum[j + 1] + f[i][j] ;
100
101 while(!que.empty() && que.front().x - j > t)//距离 大于 t 了 要出队列
102 que.pop_front();
103
104 int tmp = dp[i - 1][j] - sum[j + 1] ;
105
106 while(!que.empty() && que.back().w <= tmp)
107 que.pop_back() ;
108
109 que.push_back(node(j,tmp));
110
111 if(!que.empty())
112 dp[i][j] = max(dp[i][j],sum[j] + que.front().w );
113
114 }
115
116
117 }
118
119 int ans = dp[n - 1][1];
120 for(i = 2;i <= m;++i)
121 {
122 ans = max(ans,dp[n - 1][i]);
123 }
124 printf("%d\n",ans);
125
126
127
128 }
129 }