题意:有一个n*m(2<=n<=100 , 1<=m<=5000)的灯塔矩阵,每个灯塔有照耀周围的亮度和维护的花费,现在要在每行取一个灯塔使得相邻行的灯塔
(如(i , j),(i+1 , k))满足abs(j - k) <= light[ i ][ j ] + light[ i+1 ][ k ],问最少需要的花费是多少。
题解:很容易想到dp[ i ][ j ] = MIN(dp[ i ][ k ] + cost[ i ][ j ]),这样的时间复杂度是O(n*m*m)会T,i-1行的灯塔的照耀范围是一个区间,i 行的灯塔
也是一个区间,这样就转化为求区间最小值了,想到线段树维护区间最小值即可。
Sure原创,转载请注明出处
#include <iostream> #include <cstdio> #include <memory.h> #define MIN(a , b) ((a) < (b) ? (a) : (b)) #define MAX(a , b) ((a) > (b) ? (a) : (b)) using namespace std; const int inf = 1 << 29; const int maxn = 102; const int maxm = 5002; struct node { int l,r; int lazy,minval; }seg[maxm << 2]; int light[maxn][maxm],cost[maxn][maxm],dp[maxm]; int m,n; void read() { for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%d",&cost[i][j]); if(i == 1) dp[j] = cost[1][j]; } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%d",&light[i][j]); } } return; } void biuld(int l,int r,int num) { seg[num].l = l; seg[num].r = r; seg[num].lazy = -1; seg[num].minval = inf; if(l == r) return; int mid = (l + r) >> 1; biuld(l , mid , num << 1); biuld(mid + 1 , r , num << 1 | 1); return; } void DOWN(int num) { if(seg[num].lazy != -1) { if(seg[num << 1].lazy == -1 || seg[num << 1].lazy > seg[num].lazy) { seg[num << 1].lazy = seg[num].lazy; } if(seg[num << 1 | 1].lazy == -1 || seg[num << 1 | 1].lazy > seg[num].lazy) { seg[num << 1 | 1].lazy = seg[num].lazy; } seg[num << 1].minval = MIN(seg[num << 1].minval , seg[num].lazy); seg[num << 1 | 1].minval = MIN(seg[num << 1 | 1].minval , seg[num].lazy); seg[num].lazy = -1; } return; } void update(int l,int r,int val,int num) { if(seg[num].l == l && seg[num].r == r) { if(seg[num].lazy == -1 || seg[num].lazy > val) { seg[num].lazy = val; } seg[num].minval = MIN(seg[num].minval , val); return; } DOWN(num); int mid = (seg[num].l + seg[num].r) >> 1; if(mid >= r) update(l , r , val , num << 1); else if(l > mid) update(l , r , val , num << 1 | 1); else { update(l , mid , val , num << 1); update(mid + 1 , r , val , num << 1 | 1); } seg[num].minval = MIN(seg[num << 1].minval , seg[num << 1 | 1].minval); return; } int query(int l,int r,int num) { if(l == seg[num].l && r == seg[num].r) { return seg[num].minval; } DOWN(num); int mid = (seg[num].l + seg[num].r) >> 1; if(mid >= r) return query(l , r , num << 1); else if(l > mid) return query(l , r , num << 1 | 1); else return MIN(query(l , mid , num << 1) , query(mid + 1 , r , num << 1 | 1)); } void solve() { for(int i=2;i<=n;i++) { biuld(1 , m , 1); for(int j=1;j<=m;j++) { int l = MAX(1 , j - light[i-1][j]); int r = MIN(m , j + light[i-1][j]); update(l , r , dp[j] , 1); } for(int j=1;j<=m;j++) { int l = MAX(1 , j - light[i][j]); int r = MIN(m , j + light[i][j]); dp[j] = query(l , r , 1) + cost[i][j]; } } int res = inf; for(int i=1;i<=m;i++) { res = MIN(res , dp[i]); } printf("%d\n",res); return; } int main() { while(scanf("%d %d",&n,&m) && n+m) { read(); solve(); } return 0; }