本文主要是介绍Let the light guide us HDU - 3698，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=3698
每一行只和上下两行有关系 考虑DP dp[i][j]代表第i行第j列的最小花费
转移方程dp[i][j]=min(dp[i-1][k]) 其中k满足题中的距离要求
取最小值的过程用线段树优化一下即可
#include <bits/stdc++.h>
using namespace std;
const int N=0x3f3f3f3f;
const int maxn=1e2+10;
const int maxm=5e3+10;struct node
{int val,laz;
};node tree[maxn][4*maxm];
int t[maxn][maxm],f[maxn][maxm];
int dp[maxn][maxm];
int n,m;void change(node *tree,int val,int cur)
{tree[cur].val=min(tree[cur].val,val);tree[cur].laz=min(tree[cur].laz,val);
}void pushup(node *tree,int cur)
{tree[cur].val=min(tree[2*cur].val,tree[2*cur+1].val);
}void pushdown(node *tree,int cur)
{if(tree[cur].laz!=N){change(tree,tree[cur].laz,2*cur);change(tree,tree[cur].laz,2*cur+1);tree[cur].laz=N;}
}void build(node *tree,int l,int r,int cur)
{int m;tree[cur].val=N,tree[cur].laz=N;if(l==r) return;m=(l+r)/2;build(tree,l,m,2*cur);build(tree,m+1,r,2*cur+1);pushup(tree,cur);
}int query(node *tree,int pl,int pr,int l,int r,int cur)
{int res,m;if(pl<=l&&r<=pr) return tree[cur].val;pushdown(tree,cur);res=N,m=(l+r)/2;if(pl<=m) res=min(res,query(tree,pl,pr,l,m,2*cur));if(pr>m) res=min(res,query(tree,pl,pr,m+1,r,2*cur+1));return res;
}void update(node *tree,int pl,int pr,int val,int l,int r,int cur)
{int m;if(pl<=l&&r<=pr){change(tree,val,cur);return;}pushdown(tree,cur);m=(l+r)/2;if(pl<=m) update(tree,pl,pr,val,l,m,2*cur);if(pr>m) update(tree,pl,pr,val,m+1,r,2*cur+1);pushup(tree,cur);
}int main()
{int i,j,ans;while(scanf("%d%d",&n,&m)!=EOF){if(n==0&&m==0) break;for(i=1;i<=n;i++){for(j=1;j<=m;j++){scanf("%d",&t[i][j]);}}for(i=1;i<=n;i++){for(j=1;j<=m;j++){scanf("%d",&f[i][j]);}}for(i=1;i<=n;i++) build(tree[i],1,m,1);for(i=1;i<=n;i++){for(j=1;j<=m;j++){if(i==1) dp[i][j]=t[i][j];else dp[i][j]=query(tree[i],max(1,j-f[i][j]),min(m,j+f[i][j]),1,m,1)+t[i][j];update(tree[i+1],max(1,j-f[i][j]),min(m,j+f[i][j]),dp[i][j],1,m,1);}}ans=N;for(j=1;j<=m;j++) ans=min(ans,dp[n][j]);printf("%d\n",ans);}return 0;
}
这篇关于Let the light guide us HDU - 3698的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
