传送门:【HDU】3698 Let the light guide us
题目分析:有一个操作为| j - k | <= F( i , j ) + F ( i + 1 , k ),我们不妨把绝对值去掉。
当j < k时:k - j <= F ( i , j ) + F ( i + 1 , k ) ==> k - F( i + 1 , k ) <= F( i , j ) + j。即 i 行的区间[ j , j + F( i , j ) ]如果和i + 1行的区间[ k - F( i + 1 , k ) , k ]有交集,则称( i , j )与( i + 1 , k )互达。
当j >= k时同理。
那么问题转化成每行选择一个点使得相邻两行的点互达!
我们设dp[ i ][ j ]表示前 i 行的点已经选好以后的最小花费。
则dp[ i + 1 ][ k ] = min { dp[ i ][ j ] | 所有满足( i , j ) 与 ( i + 1 , k ) 互达的 j } + cost[ i + 1][ k ]。
当然朴素的一层一层推上去的话,复杂度高达O(nm^2),难以承受。
我们可以转化一下,假设我们知道了区间[ k - F ( i + 1 , k ) , k + F ( i + 1 , k ) ]内的最小的dp[ i ][ j ],那么是不是就可以得到dp[ i + 1][ k ]了呢?那么求区间最小值可以用线段树的区间查询来完成。
那么我们怎么知道这个区间内值都是多少?Bingo!我们可以用线段树的区间更新插入第 i 行每个 dp[ i ][ j ] 可以影响的区间[ j - F ( i , j ) , j + F ( i , j ) ],然后每个点只取能覆盖到这个点的最小的dp[ i ][ j ]。因为只有产生交集,dp[ i ][ j ]才有可能对dp[ i + 1 ][ k ]的取值有影响,所以这样算法正确性便得到了保障!
改进后的算法复杂度为O( nmlogm )。
代码如下:
#include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std ; #define REP( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i ) #define FOR( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i ) #define REV( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i ) #define travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next ) #define CLR( a , x ) memset ( a , x , sizeof a ) #define CPY( a , x ) memcpy ( a , x , sizeof a ) #define ls ( o << 1 ) #define rs ( o << 1 | 1 ) #define lson ls , l , m #define rson rs , m + 1 , r #define root 1 , 1 , m #define mid ( ( l + r ) >> 1 ) const int MAXN = 5005 ; const int INF = 0x3f3f3f3f ; int minv[MAXN << 2] , mark[MAXN << 2] ; void pushdown ( int o ) { if ( mark[o] != INF ) { minv[ls] = min ( minv[ls] , mark[o] ) ; minv[rs] = min ( minv[rs] , mark[o] ) ; mark[ls] = min ( mark[ls] , mark[o] ) ; mark[rs] = min ( mark[rs] , mark[o] ) ; mark[o] = INF ; } } void update ( int L , int R , int v , int o , int l , int r ) { if ( L <= l && r <= R ) { minv[o] = min ( minv[o] , v ) ; mark[o] = min ( mark[o] , v ) ; return ; } int m = mid ; pushdown ( o ) ; if ( L <= m ) update ( L , R , v , lson ) ; if ( m < R ) update ( L , R , v , rson ) ; minv[o] = min ( minv[ls] , minv[rs] ) ; } int query ( int L , int R , int o , int l , int r ) { if ( L <= l && r <= R ) return minv[o] ; int m = mid ; pushdown ( o ) ; if ( R <= m ) return query ( L , R , lson ) ; if ( m < L ) return query ( L , R , rson ) ; return min ( query ( L , R , lson ) , query ( L , R , rson ) ) ; } void scanf ( int& x , char c = 0 ) { while ( ( c = getchar () ) < '0' || c > '9' ) ; x = c - '0' ; while ( ( c = getchar () ) >= '0' && c <= '9' ) x = x * 10 + c - '0' ; } int n , m ; int dp[MAXN] ; int T[105][MAXN] , F[105][MAXN] ; void solve () { FOR ( i , 1 , n ) FOR ( j , 1 , m ) scanf ( T[i][j] ) ; FOR ( i , 1 , n ) FOR ( j , 1 , m ) scanf ( F[i][j] ) ; FOR ( i , 1 , m ) dp[i] = T[1][i] ; FOR ( i , 2 , n ) { CLR ( minv , INF ) ; CLR ( mark , INF ) ; FOR ( j , 1 , m ) update ( max ( 1 , j - F[i - 1][j] ) , min ( m , j + F[i - 1][j] ) , dp[j] , root ) ; FOR ( j , 1 , m ) dp[j] = query ( max ( 1 , j - F[i][j] ) , min ( m , j + F[i][j] ) , root ) + T[i][j] ; } int ans = INF ; FOR ( i , 1 , m ) if ( ans > dp[i] ) ans = dp[i] ; printf ( "%d\n" , ans ) ; } int main () { while ( ~scanf ( "%d%d" , &n , &m ) && ( n || m ) ) solve () ; return 0 ; }