题目链接：
题意：差不多就是男人勇下百层的游戏。从第一层到最后一层最多能够拿到多少分数。每层里面最多可以左右平移T个单位，同时从那个地方到下一层。一开始在第一层的X处。
首先要了解什么是单调队列，这里推荐一个博客写的很不错，直接引用了：
用dp(i,j)表示在第i层的第j个位置所能得到的最多的分数，然后这题就可以在每一层用单调队列进行双向维护dp(i,j)的值了。
具体见代码：
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 int dp[100+5][10000+5]; 8 int num[100+5][10000+5]; 9 int n,m,x,t;10 11 struct node12 {13 int id,val;14 node (int id=0,int val=0):id(id),val(val){}15 };16 void solve()17 {18 for(int i=0;i<=10000+4;i++) dp[0][i]=-0x3f3f3f3f;19 dp[0][x]=0;20 for(int i=1;i<=n;i++)21 {22 deque Q;23 for(int j=1;j<=m;j++)24 {25 int tem=dp[i-1][j]-num[i][j-1]; //从j出开始计算和的话，是减掉其前一个的26 while(!Q.empty()&&tem>Q.back().val) Q.pop_back();27 Q.push_back(node(j,tem));28 while(!Q.empty()&&j-Q.front().id>t) Q.pop_front();29 dp[i][j]=Q.front().val+num[i][j];30 }31 while(!Q.empty()) Q.pop_back();32 for(int j=m;j>=1;j--)33 {34 int tem=dp[i-1][j]+num[i][j]; //逆向维护和正向的次序相反35 while(!Q.empty()&&tem>Q.back().val) Q.pop_back();36 Q.push_back(node(j,tem));37 while(!Q.empty()&&Q.front().id-j>t) Q.pop_front();38 dp[i][j]=max(dp[i][j],Q.front().val-num[i][j-1]);39 }40 }41 int ans=dp[n][1];42 for(int i=2;i<=m;i++) ans=max(ans,dp[n][i]);43 printf("%d\n",ans);44 }45 46 int main()47 {48 while(scanf("%d%d%d%d",&n,&m,&x,&t)==4)49 {50 for(int i=1;i<=n;i++)51 for(int j=1;j<=m;j++)52 {53 scanf("%d",&num[i][j]);54 num[i][j]+=num[i][j-1];55 }56 solve();57 }58 return 0;59 }
思路倒是简单，但是被莫名其妙的坑了很久。。因为对于上面结构体里面的构造方法，写(node)(j,tem)是错误的！正确写法是node(j,tem)。因为以前使用{node}(j,tem)的写法有时候会CE，所以换了这种写法，找了很长时间的错误。。另外，在下面用tem变量时一开始用的是t，忘记和全局变量的t重复了。。悲剧啊QAQ。。。