Now there is a game called the new man down 100th floor. The rules of this game is:
　　1.  At first you are at the 1st floor. And the floor moves up. Of course you can choose which part you will stay in the first time.
　　2.  Every floor is divided into M parts. You can only walk in a direction (left or right). And you can jump to the next floor in any part, however if you are now in part “y”, you can only jump to part “y” in the next floor! (1<=y<=M)
　　3.  There are jags on the ceils, so you can only move at most T parts each floor.
　　4.  Each part has a score. And the score is the sum of the parts’ score sum you passed by.
Now we want to know after you get the 100th floor, what’s the highest score you can get.

The first line of each case has four integer N, M, X, T(1<=N<=100, 1<=M<=10000, 1<=X， T<=M). N indicates the number of layers; M indicates the number of parts. At first you are in the X-th part. You can move at most T parts in every floor in
only one direction.
Followed N lines, each line has M integers indicating the score. (-500<=score<=500)

Output the highest score you can get.

3 3 2 1
7 8 1 
4 5 6 
1 2 3 

29

#include<iostream>  //是男人就下100层   N层  各M阶 起始1层X位置 至多K步
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=100;
const int maxm=10000;
#define inf 1000000000
int n,m,X, k;
int s[maxn+5][maxm+5];
int dp[maxn+5][maxm+5];
int que[maxm*10+5],idx[maxm*10+5],head,tail;
int sol() {
    for(int i = 0; i <= n; i++) {
        for(int j = 0; j <= m; j++) {
            dp[i][j] = -inf;
        }
    }
    dp[0][X] = 0;
    for(int i=1;i<=n;i++) {
        head=1,tail=0;
        int ss=0;
        for(int j=1;j<=m;j++) {
            int temp=dp[i - 1][j]-ss;
            while(head<=tail&&que[tail]<=temp) tail--;
            que[++tail]=temp;
            idx[tail]=j;
            while(j-idx[head]>k) head++;
            ss += s[i][j];
            if(head<=tail&&que[head]+ss>dp[i][j]) dp[i][j]=que[head]+ss;
        }
        
        head=1,tail=0;
        
        ss=0;
        for(int j=m;j>=1;j--) {
            int temp=dp[i - 1][j]-ss;
            while(head<=tail&&que[tail]<=temp) tail--;
            que[++tail]=temp;
            idx[tail]=j;
            while(idx[head]-j > k) head++;
            ss+=s[i][j];
            if(head<=tail&&que[head]+ss>dp[i][j]) dp[i][j]=que[head]+ss;
        }
    }
    int maxx = -inf;
    for(int i = 1; i <= m; i++) maxx = max(maxx, dp[n][i]);
    return maxx;
}
int main() {
    while(~scanf("%d%d%d%d",&n,&m, &X, &k)) {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%d",&s[i][j]);
        printf("%d\n",sol());
    }        
}
/*
2 2 2 1
-1 -2
-1 -2
*/


还有一个比较适合理解该优化方法的题目是HDU 3401http://acm.hdu.edu.cn/showproblem.php?pid=3401



大概题目便是：一个人知道接下来T天的股市行情，想知道最终他能赚到多少钱。
构造状态dp[i][j]表示第i 天拥有 j只股票的时候，赚了多少钱
状态转移有：
1、从前一天不买不卖:
dp[i][j]=max(dp[i-1][j],dp[i][j])
2、从前i-W-1天买进一些股:
dp[i][j]=max(dp[i-W-1][k]-(j-k)*AP[i],dp[i][j])
3、从i-W-1天卖掉一些股:
dp[i][j]=max(dp[i-W-1][k]+(k-j)*BP[i],dp[i][j])
这里需要解释一下为什么只考虑第i-W-1天的买入卖出情况即可。想想看，i-W-2天是不是可以通过不买不卖将自己的最优状态转移到第i-W-1天？以此类推，之前的都不需要考虑了，只考虑都i-W-1天的情况即可。
 
对买入股票的情况进行分析，转化成适合单调队列优化的方程形式
dp[i][j]=max(dp[i-W-1][k]+k*AP[i])-j*AP[i]。令f[i-W-1][k]=dp[i-W-1][k]+k*AP[i]，则dp[i][j]=max(f[i-W-1][k]) - j*AP[i]。
这便可以用单调队列进行优化了。卖股的情况类似分析。



 #include<iostream>
 #include<string>
 using namespace std;
 #define inf 0xfffffff
 #define min(a,b) a<b?a:b
 #define max(a,b) a>b?a:b
 
 struct node
 {
     int pos;
     int f;
 };
 
 int AP[2001],BP[2001],AS[2001],BS[2001];
 int dp[2001][2001];
 node q[2001];
 int head,tail;
 int n,MaxP,W;
 
 int main()
 {
     int i,j,cas,nowf;
     freopen("D:\\in.txt","r",stdin);
     scanf("%d",&cas);
     while(cas--)
     {
         scanf("%d%d%d",&n,&MaxP,&W);
         for(i=1;i<=n;i++)
         {
             scanf("%d%d%d%d",&AP[i],&BP[i],&AS[i],&BS[i]);
         }
         for(i=0;i<=n;i++)
             for(j=0;j<=MaxP;j++)
                 dp[i][j]=-inf;
         for(i=1;i<=W+1;i++)
         {
             for(j=0;j<=(min(MaxP,AS[i]));j++)
                 dp[i][j]=-AP[i]*j;
         }
         dp[0][0]=0;
         for(i=1;i<=n;i++)
         {
             for(j=0;j<=MaxP;j++)
                 dp[i][j]=max(dp[i][j],dp[i-1][j]);
             if(i<=W+1)
                 continue;
             int pre=i-W-1; //队列里保存的是第i-W-1天的信息
             head=tail=0;
             for(j=0;j<=MaxP;j++) //因为是买，所以肯定越来越多,求DP[i][j]的时候，之前的0~~j-1的信息就存在在队列了
             {
                 nowf=dp[pre][j]+j*AP[i];
                 while(head<tail && q[tail-1].f<nowf)
                     tail--;
                 q[tail].f=nowf;q[tail++].pos=j;
                 while(head<tail && q[head].pos+AS[i]<j)
                     head++;
                 dp[i][j]=max(dp[i][j],q[head].f-j*AP[i]);
             }
             head=tail=0;
             for(j=MaxP;j>=0;j--) //因为是卖，道理同上
             {
                 nowf=dp[pre][j]+j*BP[i];
                 while(head<tail && q[tail-1].f<nowf)
                     tail--;
                 q[tail].f=nowf;q[tail++].pos=j;
                 while(head<tail && q[head].pos-BS[i]>j)
                     head++;
                 dp[i][j]=max(dp[i][j],q[head].f-j*BP[i]);
             }
         }
         int ans=0;
         for(i=0;i<=MaxP;i++)
             ans=max(ans,dp[n][i]);
         printf("%d\n",ans);
     }
     return 0;
 }