?
?
?
hdu3698 Let the light guide us dp+线段树优化(二)
<<1,l,mid); build(x<<1|1,mid+1,r); } inline void push_down(int x) { if(tree[x].col!=INF) { tree[x<<1].col=min(tree[x].col,tree[x<<1].col); tree[x<<1|1].col=min(tree[x<<1|1].col,tree[x].col); tree[x<<1].Min=min(tree[x].col,tree[x<<1].Min); tree[x<<1|1].Min=min(tree[x].col,tree[x<<1|1].Min); tree[x].col=INF; } } void update(int x,int l,int r,int val) { if(tree[x].l==l&&tree[x].r==r) { tree[x].Min=min(tree[x].Min,val); tree[x].col=min(tree[x].col,val); return; } push_down(x); int mid=(tree[x].l+tree[x].r)>>1; if(r<=mid) update(x<<1,l,r,val); else if(l>mid) update(x<<1|1,l,r,val); else { update(x<<1,l,mid,val); update(x<<1|1,mid+1,r,val); } tree[x].Min=min(tree[x<<1].Min,tree[x<<1|1].Min); } int query(int x,int l,int r) { if(tree[x].l==l&&tree[x].r==r) return tree[x].Min; push_down(x); int mid=(tree[x].l+tree[x].r)>>1; if(r<=mid) return query(x<<1,l,r); else if(l>mid) return query(x<<1|1,l,r); else return min(query(x<<1,l,mid),query(x<<1|1,mid+1,r)); } int main() { int n,m; while(~scanf(%d%d,&n,&m)) { if(n==0&&m==0) break; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf(%d,&a[i][j]); if(i==1) dp[1][j]=a[i][j]; } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf(%d,&f[i][j]); for(int i=2;i<=n;i++) { build(1,1,m); for(int j=1;j<=m;j++) { int l=max(1,j-f[i-1][j]); int r=min(m,j+f[i-1][j]); update(1,l,r,dp[i-1][j]); } for(int j=1;j<=m;j++) { int l=max(1,j-f[i][j]); int r=min(m,j+f[i][j]); dp[i][j]=query(1,l,r)+a[i][j]; } } int ans=INF; for(int i=1;i<=m;i++) ans=min(ans,dp[n][i]); printf(%d ,ans); } return 0; }