题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=116242#problem/E
题意：差不多就是男人勇下百层的游戏。从第一层到最后一层最多能够拿到多少分数。每层里面最多可以左右平移T个单位，同时从那个地方到下一层。一开始在第一层的X处。
首先要了解什么是单调队列，这里推荐一个博客写的很不错，直接引用了：http://blog.csdn.net/justmeh/article/details/5844650
用dp(i,j)表示在第i层的第j个位置所能得到的最多的分数，然后这题就可以在每一层用单调队列进行双向维护dp(i,j)的值了。
具体见代码：
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std; int dp[+][+];
int num[+][+];
int n,m,x,t; struct node
{
int id,val;
node (int id=,int val=):id(id),val(val){}
};
void solve()
{
for(int i=;i<=+;i++) dp[][i]=-0x3f3f3f3f;
dp[][x]=;
for(int i=;i<=n;i++)
{
deque<node> Q;
for(int j=;j<=m;j++)
{
int tem=dp[i-][j]-num[i][j-]; //从j出开始计算和的话，是减掉其前一个的
while(!Q.empty()&&tem>Q.back().val) Q.pop_back();
Q.push_back(node(j,tem));
while(!Q.empty()&&j-Q.front().id>t) Q.pop_front();
dp[i][j]=Q.front().val+num[i][j];
}
while(!Q.empty()) Q.pop_back();
for(int j=m;j>=;j--)
{
int tem=dp[i-][j]+num[i][j]; //逆向维护和正向的次序相反
while(!Q.empty()&&tem>Q.back().val) Q.pop_back();
Q.push_back(node(j,tem));
while(!Q.empty()&&Q.front().id-j>t) Q.pop_front();
dp[i][j]=max(dp[i][j],Q.front().val-num[i][j-]);
}
}
int ans=dp[n][];
for(int i=;i<=m;i++) ans=max(ans,dp[n][i]);
printf("%d\n",ans);
} int main()
{
while(scanf("%d%d%d%d",&n,&m,&x,&t)==)
{
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%d",&num[i][j]);
num[i][j]+=num[i][j-];
}
solve();
}
return ;
}
思路倒是简单，但是被莫名其妙的坑了很久。。因为对于上面结构体里面的构造方法，写(node)(j,tem)是错误的！正确写法是node(j,tem)。因为以前使用{node}(j,tem)的写法有时候会CE，所以换了这种写法，找了很长时间的错误。。另外，在下面用tem变量时一开始用的是t，忘记和全局变量的t重复了。。悲剧啊QAQ。。。