POJ3926 - 很少人做的单调队列优化DP..

首先日西一下...Van_Persie是我的小号..zzyzzy12是我的大号..囧...上面是按空间排序..下面是按时间排序...时间排第七...空间居然是第一..好吧！！晒得果断！

回到正题..这道题是上个周末在衡阳八中跟他们一起训练做的...当时只过了6个点...回来再POJ上A发现更多问题...题意我就不再说明了..注意的是这里的长度不会影响上下..也就是说整个可以看成一个每个格子相等的矩阵...长度只是代表一个数~~不是说每个格子的边长..否则没法做了...

首先是输入很恶心..数据量很大...用scanf光OI就超时..所以只能先gets一行字符再来自己转...

dp方程也比较好想吧...dp[ k ] [ i ] 代表到达第k行第i个路口能取到的最大值...dp从第一行开始做到最后一行...

题目最原始的做法是一行一行往上做..首先将下一行的值copy上来(上下走不要距离代价)..然后枚举每个点左走到能走的路口更新...右走到能走的路口更新..这样的话最强数据的运算次数将是 10^5*10^5*100 给的1S...铁定超时..

看状态转移方程...我是没想出其他的了...那就在状态转移的时候做优化...每一个点向左扫描更新到能更新到的距离...向右扫描更新到能更新到的距离..可以想象每次更新只能更新到特定的一个长度..并且长度是非降的..所以用单调队列..

这里每行做两次扫描....一次从左向右...一次从右向左..分开做两次扫描...先更新单调队列..也就是从头结点挤掉距离大于L的...从尾挤掉更新值小于当前点的..再插在尾结点的后面..用头结点来更新当前点的dp值...

为了处理方便...开始在读入时...就可以把每个点的长度以及快乐值都置成1到当前点的之和...方便后面dp时得出一段的距离长度或者一段的快乐值~~~

读入时千万要注意快乐值可能是负的~~用字符串读得时候要多判断一下~~

我的空间少就是因为我的长度是边读边做的~~~dp是滚动数组的~~

Program:

#include<iostream>  
#define oo 1000000000
#define MAXN 10015
using namespace std; 
int n,m,L,i,j,k,p,x,h1,h2,line[MAXN],pop[115][MAXN],len[MAXN],dp[2][MAXN],ans;  
char s[2000001]; 
int getint()
{
    int data=0,u=1;
    while (s[x]<'0' || s[x]>'9' ) x++;
    if (x && s[x-1]=='-')  u=-1;
    while (s[x]>='0' && s[x]<='9') 
    {
          data=data*10+s[x]-'0';  
          x++;
    }
    return data*u;    
}
int main()
{ 
    while (gets(s))
    {
          x=0;
          n=getint(); m=getint(); L=getint();
          if (!n && !m && !L) break;    
          for (i=1;i<=n+1;i++)
          {
                gets(s); x=0;
                pop[i][0]=0;
                for (j=1;j<=m;j++) 
                {
                     pop[i][j]=getint();
                     pop[i][j]+=pop[i][j-1];
                } 
          } 
          p=1;  len[0]=0;
          memset(dp[p],0,sizeof(dp[p]));
          for (k=1;k<=n+1;k++)
          {
                p=1-p; 
                gets(s); x=0;
                for (i=1;i<=m;i++) 
                {
                      len[i]=getint();
                      len[i]+=len[i-1];    
                }
                memset(dp[p],0,sizeof(dp[p]));
                h1=1; h2=0;
                for (i=0;i<=m;i++)
                { 
                      while (h1<=h2 && len[i]-len[line[h1]]>L) h1++; 
                      while (h1<=h2 && dp[1-p][line[h2]]+pop[k][i]-pop[k][line[h2]]<=dp[1-p][i]) h2--;
                      line[++h2]=i; 
                      dp[p][i]=dp[1-p][line[h1]]+pop[k][i]-pop[k][line[h1]];               
                }//  单调队列1 左往右 
                h1=1; h2=0; 
                for (i=m;i>=0;i--)
                { 
                      while (h1<=h2 && len[line[h1]]-len[i]>L) h1++; 
                      while (h1<=h2 && dp[1-p][line[h2]]+pop[k][line[h2]]-pop[k][i]<=dp[1-p][i]) h2--;
                      line[++h2]=i;                   
                      if (dp[p][i]<dp[1-p][line[h1]]+pop[k][line[h1]]-pop[k][i])  
                          dp[p][i]=dp[1-p][line[h1]]+pop[k][line[h1]]-pop[k][i];      
                }//  单调队列2 右往左                            
          }    
          ans=0;
          for (i=0;i<=m;i++) ans=ans>dp[p][i]?ans:dp[p][i];
          printf("%d\n",ans);  
    }
    return 0;
}