题意：在每行上选一个点，每个点都要各自对应的代价，同时相邻两行的点要满足 |j-k|≤f(i,j)+f(i+1,k)。问最小代价是多少。

 

题解：

不难发现这是一道dp，状态转移方程如下$dp[i][j]=min\{dp[i-1][k]\}+t[i][j](|j-k|≤f(i,j)+f(i+1,k))$

然而如果直接进行转移是要T飞的

所以如何快速求$k$呢？

可以发现，$dp[i-1][k]$只会对一个区间的答案产生影响，而$dp[i][j]$的答案必定是一个区间中的最小值加上自己的时间

于是就是区间修改和区间查询了，之间上线段树

ps：因为$dp$数组每一行都会更新，实际上可以省掉第一维的空间

1 //minamoto 2 #include
     
       3 #include
      
        4 using namespace std; 5 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 6 char buf[1<<21],*p1=buf,*p2=buf; 7 template
       
        inline bool cmin(T&a,const T&b){
   return a>b?a=b,1:0;} 8 inline int read(){ 9     #define num ch-'0'10     char ch;bool flag=0;int res;11     while(!isdigit(ch=getc()))12     (ch=='-')&&(flag=true);13     for(res=num;isdigit(ch=getc());res=res*10+num);14     (flag)&&(res=-res);15     #undef num16     return res;17 }18 char sr[1<<21],z[20];int C=-1,Z;19 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}20 inline void print(int x){21     if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;22     while(z[++Z]=x%10+48,x/=10);23     while(sr[++C]=z[Z],--Z);sr[++C]='\n';24 }25 const int N=105,M=5005,inf=0x3f3f3f3f;26 int t[N][M],f[N][M],dp[M],sum[M<<2],add[M<<2];27 int n,m;28 void pushdown(int p){29     if(add[p]!=inf){30         cmin(add[p<<1],add[p]),cmin(add[p<<1|1],add[p]);31         cmin(sum[p<<1],add[p<<1]),cmin(sum[p<<1|1],add[p<<1|1]);32         add[p]=inf;33     }34 }35 void build(int l,int r,int p){36     sum[p]=add[p]=inf;37     if(l==r) return;38     int mid=l+r>>1;39     build(l,mid,p<<1),build(mid+1,r,p<<1|1);40 }41 void update(int ql,int qr,int x,int l,int r,int p){42     if(ql<=l&&qr>=r){43         cmin(add[p],x),cmin(sum[p],add[p]);return;44     }45     int mid=l+r>>1;46     pushdown(p);47     if(ql<=mid) update(ql,qr,x,l,mid,p<<1);48     if(qr>mid) update(ql,qr,x,mid+1,r,p<<1|1);49     sum[p]=min(sum[p<<1],sum[p<<1|1]);50 }51 int query(int ql,int qr,int l,int r,int p){52     if(ql<=l&&qr>=r) return sum[p];53     int mid=l+r>>1;54     pushdown(p);55     int res=inf;56     if(ql<=mid) cmin(res,query(ql,qr,l,mid,p<<1));57     if(qr>mid) cmin(res,query(ql,qr,mid+1,r,p<<1|1));58     return res;59 }60 int main(){61     //freopen("testdata.in","r",stdin);62     while(true){63         n=read(),m=read();64         if(n==0&&m==0) break;65         for(int i=1;i<=n;++i)66         for(int j=1;j<=m;++j)67         t[i][j]=read();68         for(int i=1;i<=n;++i)69         for(int j=1;j<=m;++j)70         f[i][j]=read();71         for(int i=1;i<=m;++i) dp[i]=t[1][i];72         for(int i=2;i<=n;++i){73             build(1,m,1);74             for(int j=1;j<=m;++j)75             update(j-f[i-1][j],j+f[i-1][j],dp[j],1,m,1);76             for(int j=1;j<=m;++j)77             dp[j]=query(j-f[i][j],j+f[i][j],1,m,1)+t[i][j];78         }79         int ans=inf;80         for(int i=1;i<=m;++i) cmin(ans,dp[i]);81         print(ans);82     }83     Ot();84     return 0;85 }