hdu 3698 Let the light guide us(线段树优化&简单DP)

Let the light guide usTime Limit: 5000/2000 MS (Java/Others)    Memory Limit: 62768/32768 K (Java/Others)
Total Submission(s): 677    Accepted Submission(s): 226


Problem DescriptionInputOutputSample InputSample OutputSourceRecommend#include<algorithm>#include<iostream>#include<sstream>#include<string.h>#include<stdio.h>#include<math.h>#include<vector>#include<string>#include<queue>#include<map>using namespace std;const int INF=0x3f3f3f3f;const int maxn=150;const int maxm=5010;int ti[maxn][maxm],f[maxn][maxm],minv[maxm<<2],lazy[maxm<<2];int dp[maxm],n,m;void btree(int L,int R,int k){ int ls,rs,mid; minv[k]=lazy[k]=INF; if(L==R) return ; ls=k<<1; rs=ls|1; mid=(L+R)>>1; btree(L,mid,ls); btree(mid+1,R,rs);}void pushdown(int k,int ls,int rs){ minv[ls]=min(minv[ls],lazy[k]); minv[rs]=min(minv[rs],lazy[k]); lazy[ls]=min(lazy[ls],lazy[k]); lazy[rs]=min(lazy[rs],lazy[k]); lazy[k]=INF;}void update(int L,int R,int l,int r,int k,int v){ int ls,rs,mid; if(L==l&&R==r) { minv[k]=min(minv[k],v); lazy[k]=min(lazy[k],v); return; } ls=k<<1; rs=ls|1; mid=(L+R)>>1; if(lazy[k]!=INF) pushdown(k,ls,rs); if(l>mid) update(mid+1,R,l,r,rs,v); else if(r<=mid) update(L,mid,l,r,ls,v); else { update(L,mid,l,mid,ls,v); update(mid+1,R,mid+1,r,rs,v); } minv[k]=min(minv[ls],minv[rs]);}int qu(int L,int R,int l,int r,int k){ int ls,rs,mid; if(L==l&&R==r) return minv[k]; ls=k<<1; rs=ls|1; mid=(L+R)>>1; if(lazy[k]!=INF) pushdown(k,ls,rs); if(l>mid) return qu(mid+1,R,l,r,rs); else if(r<=mid) return qu(L,mid,l,r,ls); else return min(qu(L,mid,l,mid,ls),qu(mid+1,R,mid+1,r,rs));}int main(){ int i,j,l,r,ans; while(scanf("%d%d",&n,&m),n||m) { for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&ti[i][j]); for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&f[i][j]); for(i=1;i<=m;i++) dp[i]=ti[1][i]; for(i=2;i<=n;i++) { btree(1,m,1); for(j=1;j<=m;j++) { l=max(j-f[i-1][j],1); r=min(j+f[i-1][j],m); update(1,m,l,r,1,dp[j]); } for(j=1;j<=m;j++) { l=max(j-f[i][j],1); r=min(j+f[i][j],m); dp[j]=qu(1,m,l,r,1)+ti[i][j]; } } ans=INF; for(i=1;i<=m;i++) ans=min(ans,dp[i]); printf("%d\n",ans); } return 0;}