Original link: https://blog.chungzh.cn/articles/luogu-p2254/
“NOI2005” Magnificent Waltz
meaning of the title
Think of the ballroom as a matrix of $N$ rows and $M$ columns, where some squares are stacked with furniture and others are empty spaces. The piano can slide in the clearing, but it cannot hit the furniture or slide out of the ballroom, otherwise it will damage the piano and furniture, attracting a difficult captain. At each moment, the piano slides one square to the adjacent square, which can be east, west, south or north, as the hull tilts. And Emily can choose to use magic or no magic: if not, the piano will slide; if magic, the piano will stay in place.
Emily is an angel who knows the tilt of the hull every time. She wanted to make the piano slide as long as possible in the ballroom, so 1900 would be very happy, and also good for curing Tony’s seasickness. But Emily is too young to count, so hopefully you can help her.
In the data of $100%$, $1\leq N, M \leq 200$, $K \leq 200$, $T\leq 40000$.
analyze
First we define the state. Let $dp[t][i][j]$ denote the length of the longest gliding distance in $(i, j)$ at time t. The state transition equation is $dp[t][i][j] = \max(dp[t-1][i][j], dp[t-1][i^{‘}][j^{‘ }])$, $i^{‘}$ and $j^{‘}$ are legal past positions, depending on the direction the hull is leaning at $t$.
If the state is designed in this way, the time complexity is $O(TNM)$, and space seems to be an issue.
At this time, we found that there is another variable $K$ that is not used. Consider setting the state to $dp[t][i][j]$ to indicate that in the $t$ time period, in $(i, j)$ The longest run length to glide. The time complexity is $O(KN^3)$, not yet.
Let’s see if we can optimize it further. The following assumes that the current direction of the hull inclination is east. Let the length of the current time period be $tim$, and the position of the piano in the previous time period is $(i, m)$, then $dp[t][i][j] = \max_{jm<=tim}{dp[ t-1][i][m]+jm}$. In this formula, there is only one variable $m$, and $jm<=tim$, the legal decision is in an adjacent interval, and monotonic queue optimization can be used!
For two decisions $m_1 < m_2$, $m_2$ is better than $m_1$ only if:
$$
dp[t-1][i][m_1]+(j-m_1) < dp[t-1][i][m_2]+(j-m_2) \
dp[t-1][i][m+1]+m_2-m_1 < dp[t-1][i][m_2]
$$
When a new decision is added to the tail of the monotonic queue, we use this formula to determine whether the tail of the queue needs to be dequeued or not to maintain monotonicity.
This reduces the time complexity to $KN^2$.
Attention to detail:
- Illegal ($-1$) decisions do not enqueue
RECORD
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128
|
#include <bits/stdc++.h> using namespace std ; int n , m , x , y , k ; char a [ 205 ][ 205 ]; int s [ 205 ], t [ 205 ], d [ 205 ]; int dp [ 205 ][ 205 ][ 205 ]; struct deq { int head , tail ; int arr [ 20005 ]; bool empty () { return head + 1 == tail ; } void pop_front () { head ++ ; } void pop_back () { tail -- ; } void push_back ( int x ) { arr [ tail ] = x ; tail ++ ; } void clear () { head = 0 ; tail = 1 ; } int front () { return arr [ head + 1 ]; } int back () { return arr [ tail - 1 ]; } } q ; int main () { cin >> n >> m >> x >> y >> k ; for ( int i = 1 ; i <= n ; i ++ ) for ( int j = 1 ; j <= m ; j ++ ) cin >> a [ i ][ j ]; memset ( dp , - 1 , sizeof ( dp )); dp [ 0 ][ x ][ y ] = 0 ; int ans = 1 ; for ( int p = 1 ; p <= k ; p ++ ) { cin >> s [ p ] >> t [ p ] >> d [ p ]; int tim = t [ p ] - s [ p ] + 1 ; // 下面进行对四个方向的分类讨论if ( d [ p ] == 1 ) { for ( int j = 1 ; j <= m ; j ++ ) { q . clear (); for ( int i = n ; i >= 1 ; i -- ) { if ( a [ i ][ j ] == 'x' ) { q . clear (); continue ; } dp [ p ][ i ][ j ] = dp [ p - 1 ][ i ][ j ]; while ( ! q . empty () && q . front () - i > tim ) q . pop_front (); if ( ! q . empty ()) { dp [ p ][ i ][ j ] = max ( dp [ p ][ i ][ j ], dp [ p - 1 ][ q . front ()][ j ] + q . front () - i ); ans = max ( ans , dp [ p ][ i ][ j ]); } while ( ! q . empty () && dp [ p - 1 ][ i ][ j ] - dp [ p - 1 ][ q . back ()][ j ] >= q . back () - i ) q . pop_back (); if ( dp [ p - 1 ][ i ][ j ] != - 1 ) q . push_back ( i ); } } } else if ( d [ p ] == 2 ) { for ( int j = 1 ; j <= m ; j ++ ) { q . clear (); for ( int i = 1 ; i <= n ; i ++ ) { if ( a [ i ][ j ] == 'x' ) { q . clear (); continue ; } dp [ p ][ i ][ j ] = dp [ p - 1 ][ i ][ j ]; while ( ! q . empty () && i - q . front () > tim ) q . pop_front (); if ( ! q . empty ()) { dp [ p ][ i ][ j ] = max ( dp [ p ][ i ][ j ], dp [ p - 1 ][ q . front ()][ j ] + i - q . front ()); ans = max ( ans , dp [ p ][ i ][ j ]); } while ( ! q . empty () && dp [ p - 1 ][ i ][ j ] - dp [ p - 1 ][ q . back ()][ j ] >= i - q . back ()) q . pop_back (); if ( dp [ p - 1 ][ i ][ j ] != - 1 ) q . push_back ( i ); } } } else if ( d [ p ] == 3 ) { for ( int i = 1 ; i <= n ; i ++ ) { q . clear (); for ( int j = m ; j >= 1 ; j -- ) { if ( a [ i ][ j ] == 'x' ) { q . clear (); continue ; } dp [ p ][ i ][ j ] = dp [ p - 1 ][ i ][ j ]; while ( ! q . empty () && q . front () - j > tim ) q . pop_front (); if ( ! q . empty ()) { dp [ p ][ i ][ j ] = max ( dp [ p ][ i ][ j ], dp [ p - 1 ][ i ][ q . front ()] + q . front () - j ); ans = max ( ans , dp [ p ][ i ][ j ]); } while ( ! q . empty () && dp [ p - 1 ][ i ][ j ] - dp [ p - 1 ][ i ][ q . back ()] >= q . back () - j ) q . pop_back (); if ( dp [ p - 1 ][ i ][ j ] != - 1 ) q . push_back ( j ); } } } else { for ( int i = 1 ; i <= n ; i ++ ) { q . clear (); for ( int j = 1 ; j <= m ; j ++ ) { if ( a [ i ][ j ] == 'x' ) { q . clear (); continue ; } dp [ p ][ i ][ j ] = dp [ p - 1 ][ i ][ j ]; while ( ! q . empty () && j - q . front () > tim ) q . pop_front (); if ( ! q . empty ()) { dp [ p ][ i ][ j ] = max ( dp [ p ][ i ][ j ], dp [ p - 1 ][ i ][ q . front ()] + j - q . front ()); ans = max ( ans , dp [ p ][ i ][ j ]); } while ( ! q . empty () && dp [ p - 1 ][ i ][ j ] - dp [ p - 1 ][ i ][ q . back ()] >= j - q . back ()) q . pop_back (); if ( dp [ p - 1 ][ i ][ j ] != - 1 ) q . push_back ( j ); } } } } cout << ans << endl ; return 0 ; }
|
This article is reproduced from: https://blog.chungzh.cn/articles/luogu-p2254/
This site is for inclusion only, and the copyright belongs to the original author.