【线段树优化DP】 HDU 3698 Let the light guide us

 1 // #include <bits/stdc++.h>
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <queue>
 5 #include <cstring>
 6 #include <cctype>
 7 #include <set>
 8 #include <cmath>
 9 #define For(i,a,b) for(int i=a;i<=b;++i)
10 #define Dec(i,b,a) for(int i=b;i>=a;--i)
11 #define file() freopen("c://users/asus/desktop/v.txt","r",stdin);
12 #define inf 0x3f3f3f3f
13 using namespace std;
14 
15 typedef long long ll;
16 inline ll qr(){
17     ll x=0,f=1; char ch;
18     while(!isdigit(ch=getchar())) if(ch==‘-‘) f=-1;
19     for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
20     return x*f;
21 }
22 // #define cmin(x,y) (x>y?x=y:0)
23 void cmin(int &x,int y){if(x>y)x=y;}
24 #define mid (l+r>>1)
25 #define lc x<<1
26 #define rc x<<1|1
27 const int N = 5010;
28 int g[N<<2],mn[N<<2];
29 int f[101][N],a[101][N],d[N];
30 void down(int x)
31 {
32     if(g[x]!=inf)
33     {
34         cmin(mn[lc],g[x]); cmin(mn[rc],g[x]);
35         cmin(g[lc],g[x]); cmin(g[rc],g[x]); g[x]=inf;
36     }
37 }
38 void build(int x,int l,int r)
39 {
40     mn[x]=g[x]=inf;
41     if(l==r) return;
42     build(lc,l,mid); build(rc,mid+1,r);
43 }
44 void upd(int x,int l,int r,int L,int R,int k)
45 {
46     if(L<=l&&r<=R) return (void)(cmin(g[x],k),cmin(mn[x],k));
47     down(x);
48     if(L<=mid) upd(lc,l,mid,L,R,k);
49     if(R>mid) upd(rc,mid+1,r,L,R,k);
50     mn[x]=min(mn[lc],mn[rc]);
51 }
52 int qry(int x,int l,int r,int L,int R)
53 {
54     if(L<=l&&r<=R) return mn[x];
55     down(x);
56     int s=inf;
57     if(L<=mid) cmin(s,qry(lc,l,mid,L,R));
58     if(R>mid) cmin(s,qry(rc,mid+1,r,L,R));
59     return s;
60 }
61 int main()
62 {
63     // file();
64     while(1)
65     {
66         int n=qr(),m=qr();
67         if(!n) break;
68         For(i,1,n) For(j,1,m) a[i][j]=qr();
69         For(i,1,n) For(j,1,m) f[i][j]=qr();
70         For(i,1,m) d[i]=a[1][i];
71         For(i,2,n)
72         {
73             build(1,1,m);
74             For(j,1,m) upd(1,1,m,j-f[i-1][j],j+f[i-1][j],d[j]);
75             For(j,1,m) d[j]=qry(1,1,m,j-f[i][j],j+f[i][j])+a[i][j];
76         }
77         int ans=inf;
78         For(i,1,m) cmin(ans,d[i]);
79         printf("%d\n", ans);
80     }
81     return 0;
82 }