题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3698
题目大意：给你$n imes m$的表格，你在每一行必须且只能放置一个塔，在每个格子建造塔的时间为$a[i][j]$，魔法范围为$mg[i][j]$，相邻两行的塔设为$(i,j)(i+1,k)$必须满足$|j-k|<=mg[i][j]+mg[i+1][k]$
Sample Input
3 5 9 5 3 8 7 8 2 6 8 9 1 9 7 8 6 0 1 0 1 2 1 0 2 1 1 0 2 1 0 2 0 0
Sample Output
10
emmm,最朴素的DP是很好想的，设置DP状态为dp[i][j]表示第i行在第j列放置塔的最小花费时间。然后每次寻找上一层合适的位置，这样一来复杂度为$O(NM^2)$，代码如下：
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int mac=5e3+10; const int inf=1e9+10; int dp[120][mac],time[120][mac],mg[120][mac]; //第i行在第j列建造的最优值 bool ok(int i,int j,int p,int k) { return abs(j-k)<=mg[i][j]+mg[p][k]; } int main() { int n,m; while (scanf ("%d%d",&n,&m)){ if (!n && !m) return 0; for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) scanf ("%d",&time[i][j]); for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) scanf ("%d",&mg[i][j]); for (int i=1; i<=m; i++) dp[1][i]=time[1][i]; for (int i=2; i<=n; i++){ for (int j=1; j<=m; j++){ dp[i][j]=inf; for (int k=1; k<=m; k++) if (ok(i,j,i-1,k)) dp[i][j]=min(dp[i][j],dp[i-1][k]+time[i][j]); } } /*for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) printf("%d%c",dp[i][j],j==m?' ':' ');*/ int ans=inf; for (int i=1; i<=m; i++) ans=min(dp[n][i],ans); printf("%d ",ans); } return 0; }
注意到第x行每个位置辐射的范围为$(j-mg[x][j],j+mg[x][j])$，那么如果上一行中有范围和它重合，那么就构成了答案。我们要从上一层的每个范围进行覆盖并取最小值，那么很明显可以用线段树来做，也就是区间置换+求最小值。
emmmm，不过，似乎很久没写线段树了。。。QAQ卡了将近2小时的线段树BUG
以下是AC代码：
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int mac=5e3+10; const int inf=1e9+10; #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 int dp[120][mac],time[120][mac],mg[120][mac]; //第i行在第j列建造的最优值 struct node { int val,f; }tree[mac<<2]; void push_down(int rt) { int lc=rt<<1,rc=rt<<1|1; tree[lc].f=min(tree[lc].f,tree[rt].f); tree[rc].f=min(tree[rc].f,tree[rt].f); if (tree[lc].val>tree[rt].f) tree[lc].val=tree[rt].f; if (tree[rc].val>tree[rt].f) tree[rc].val=tree[rt].f; tree[rt].f=inf; } void push_up(int rt) { int lc=rt<<1,rc=rt<<1|1; tree[rt].val=min(tree[lc].val,tree[rc].val); } void build(int l,int r,int rt) { tree[rt].val=inf,tree[rt].f=inf; if (l==r) return; int mid=(l+r)>>1; build(lson);build(rson); } void update(int l,int r,int rt,int L,int R,int val) { if (l>=L && r<=R){ tree[rt].f=min(tree[rt].f,val); tree[rt].val=min(tree[rt].val,val); return; } if (tree[rt].f!=inf) push_down(rt); int mid=(l+r)>>1; if (mid>=L) update(lson,L,R,val); if (mid<R) update(rson,L,R,val); push_up(rt); } int query(int l,int r,int rt,int L,int R) { int ans=inf; if (l>=L && r<=R){ return tree[rt].val; } if (tree[rt].f!=inf) push_down(rt); int mid=(l+r)>>1; if (mid>=L) ans=min(ans,query(lson,L,R)); if (mid<R) ans=min(ans,query(rson,L,R)); return ans; } int main() { int n,m; while (scanf ("%d%d",&n,&m)){ if (!n && !m) return 0; for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) scanf ("%d",&time[i][j]); for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) scanf ("%d",&mg[i][j]); for (int i=1; i<=m; i++) dp[1][i]=time[1][i]; for (int i=2; i<=n; i++){ build(1,m,1); for (int j=1; j<=m; j++){ update(1,m,1,max(1,j-mg[i-1][j]),min(m,j+mg[i-1][j]),dp[i-1][j]); } for (int j=1; j<=m; j++){ dp[i][j]=inf; int s=query(1,m,1,max(1,j-mg[i][j]),min(m,j+mg[i][j])); dp[i][j]=min(dp[i][j],s+time[i][j]); } } int ans=inf; for (int i=1; i<=m; i++) ans=min(dp[n][i],ans); printf("%d ",ans); } return 0; }