题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1499
可以很容易的写出DP方程f[t][i][j]=max(f[t-1][i][j],f[t-1][last(i)][last(j)]+1)，但是这个DP的总复杂度是O(nmT)，会TLE，所以不用时间来划分状态，而是使用时段来划分状态，h表示第h个时间段，那么f[h][i][j]=max(f[h-1][last(i)][last(j)]+dist(i,j,last(i),last(j)))，这个方程直接转移状态是O（n），但是我们可以使用单调队列优化维护决策到O(1)，那么DP复杂度就成了O(nmk)，可以AC。
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <deque>
using namespace std ;
#define MAXN 210
#define MAXK 210
#define rep( i , x )for(int i =0; i ++< x ;)
#define dow( i , x )for(int i = x ; i ;-- i )
char map[ MAXN ][ MAXN ];
int f[ MAXN ][ MAXN ][ MAXN ], n , m , k , x , y ;
deque <int> Q ;
int main( ){
scanf("%d%d%d%d%d",&n ,&m ,&x ,&y ,&k );
rep( i , n )scanf("%s", map[ i ]+1);
rep( i , n )rep( j , m ) f[0][ i ][ j ]=-1;
f[0][ x ][ y ]=0;
rep( h , k ){
int l , r , d ;scanf("%d%d%d",&l ,&r ,&d );
rep( i , n )rep( j , m ) f[ h ][ i ][ j ]=-1;
if( d ==1){
rep( j , m ){
Q.clear( );
dow( i , n )if( map[ i ][ j ]=='.'){
while(! Q.empty( )&& Q.front( )- i > r - l +1) Q.pop_front( );
if( f[ h -1][ i ][ j ]!=-1){
while(! Q.empty( )&& Q.back( )- i + f[ h -1][ Q.back( )][ j ]<= f[ h -1][ i ][ j ]) Q.pop_back( );
Q.push_back( i );
}
if(! Q.empty( )) f[ h ][ i ][ j ]= f[ h -1][ Q.front( )][ j ]+ Q.front( )- i ;
else f[ h ][ i ][ j ]=-1;
}else{
Q.clear( ); f[ h ][ i ][ j ]=-1;
}
}
}else if( d ==2){
rep( j , m ){
Q.clear( );
rep( i , n )if( map[ i ][ j ]=='.'){
while(! Q.empty( )&& i - Q.front( )> r - l +1) Q.pop_front( );
if( f[ h -1][ i ][ j ]!=-1){
while(! Q.empty( )&& i - Q.back( )+ f[ h -1][ Q.back( )][ j ]<= f[ h -1][ i ][ j ]) Q.pop_back( );
Q.push_back( i );
}
if(! Q.empty( )) f[ h ][ i ][ j ]= f[ h -1][ Q.front( )][ j ]+ i - Q.front( );
else f[ h ][ i ][ j ]=-1;
}else{
Q.clear( ); f[ h ][ i ][ j ]=-1;
}
}
}else if( d ==3){
rep( i , n ){
Q.clear( );
dow( j , m )if( map[ i ][ j ]=='.'){
while(! Q.empty( )&& Q.front( )- j > r - l +1) Q.pop_front( );
if( f[ h -1][ i ][ j ]!=-1){
while(! Q.empty( )&& Q.back( )- j + f[ h -1][ i ][ Q.back( )]<= f[ h -1][ i ][ j ]) Q.pop_back( );
Q.push_back( j );
}
if(! Q.empty( )) f[ h ][ i ][ j ]= Q.front( )- j + f[ h -1][ i ][ Q.front( )];
else f[ h ][ i ][ j ]=-1;
}else{
Q.clear( ); f[ h ][ i ][ j ]=-1;
}
}
}else{
rep( i , n ){
Q.clear( );
rep( j , m )if( map[ i ][ j ]=='.'){
while(! Q.empty( )&& j - Q.front( )> r - l +1) Q.pop_front( );
if( f[ h -1][ i ][ j ]!=-1){
while(! Q.empty( )&& j - Q.back( )+ f[ h -1][ i ][ Q.back( )]<= f[ h -1][ i ][ j ]) Q.pop_back( );
Q.push_back( j );
}
if(! Q.empty( )) f[ h ][ i ][ j ]= j - Q.front( )+ f[ h -1][ i ][ Q.front( )];
else f[ h ][ i ][ j ]=-1;
}else{
Q.clear( ); f[ h ][ i ][ j ]=-1;
}
}
}
}
int ans =0;
rep( i , n )rep( j , m ) ans =max( ans , f[ k ][ i ][ j ]);
printf("%d\n", ans );
return 0;
}
网友评论