[Problem Description]
Do you skip the waltz ? When the music starts , When you slide to the melody , Is there a kind of pleasure to walk in fairyland ? as everyone knows , When Waltz , The most important thing is to have good music . But few people know , The greatest pianist in the world has been adrift on the sea all his life , His name is Denny • Budman •T.D.• lemon •1900, His friends call him 1900.
1900 stay 20 In the first year of the century, she was born on the cruise ship Virginia between Europe and America , Unfortunately, he was abandoned at birth , Became an orphan .1900 Growing up alone on the Virginia , Never left this shaking world . Maybe it's compensation for his fate , God sent the lovely little angel Emily to take care of him . Maybe it's an angel's touch ,1900 With incredible piano talent ： It's never been taught , Never read a score , But he can play the most refreshing melody with his own feeling . When 1900 When the music was welcomed by everyone on the cruise , He is talented 8 year , At this time, he had been sailing to and from Europe and America 50 The rest of the time . Although it's a piano prodigy , but 1900 Still a child , He has the same curiosity and mischievous as ordinary boys , It's just a little bit more romantic ： It was a stormy night , The sea breeze whipped waves against the Virginia , The cruise ship swayed violently with the huge waves . Max, the new saxophone player on the ship • Tony is seasick ,1900 Ask Tony to sit on the piano in the ballroom with him , Then the brake that held the piano was released , therefore , The piano slid along with the incline of the ship . Exactly , Our protagonist 1900, piano , Cruise ship with 1900 The melody of the dance waltz together , along with “ Bang, Cha, cha ” The rhythm of , Tony's seasickness also miraculously disappeared . Later Tony wrote in his memoir ： The sea rocked us, and we whirled around quickly over the lights and furniture, and I realized that we were dancing with the sea. It was perfect and crazy dancers. Isn't it nice to waltz happily on the golden floor at night ? perhaps , We forget a person , That's Emily , She's not free ： She had to cast magic help at the right time 1900, Keep the piano out of the ballroom furniture . Think of the ballroom as a N That's ok M Matrix of columns , Some of the squares in the matrix are stacked with furniture , The others are open spaces . The piano can slide across the open space , But don't bump into furniture or slide out of the ballroom , Otherwise, the piano and furniture will be damaged , Attracting a difficult Captain . Every moment , The piano will slide one space in the direction of the inclination of the hull to the adjacent square , Adjacent squares can be oriented East , To the West , South or North . And Emily can choose to do magic or not ： If you don't do magic , Then the piano will slide ; If you do magic , The piano will not move . Emily is an angel , She knew the inclination of the hull at each time . She wanted to make the piano slide as long as possible in the ballroom , such 1900 Will be very happy , It also helps to treat Tony's seasickness . But Emily is still too young , It doesn't count , So I hope you can help her .
[Algorithm] DP + optimization [Analysis]
O(NMT) Of DP It's better to think about it . set up f[p][i][j] express p Time out (i,j) The maximum number of steps that can be taken when . be f[p][i][j] = max(f[p -
1][i][j], f[p - 1][i - dx][j - dy], among dx, dy
It's the direction of movement at this moment . Of course, it's going to be overtime . We can optimize by taking advantage of the same direction of movement in a period of time . For example, the current is a duration of 0 5s Time period of , The moving direction is right . We deal with each line separately . First, we will f[p
- 1][i] Add to each point in (m - j +
1)（ We assume that the ordinate is j, This is because the more left you can take, the more steps you can take ）, Then scan it from left to right , It can be maintained by monotone queue . This reduces the time efficiency to O(NMK), Perfect solution .
[Pay Attention] Don't forget to consider obstacles [Code]
/************************************************************** Problem: 1499
User: gaotianyu1350 Language: C++ Result: Accepted Time:1180 ms Memory:2076 kb
****************************************************************/ #include
<cstdio> #include <cmath> #include <cstdlib> #include <cstring> #include
<deque> #include <iostream> using namespace std; const int MAXN = 300; const
int MAXK = 300; const int d[4][2] = {{-1, 0}, {1, 0}, {-1, 0}, {0, 1}}; int
f[2][MAXN][MAXN]; int startx, starty, n, m, k; int start[MAXK], end[MAXK],
dir[MAXK]; char map[MAXN][MAXN]; int New, Old; struct MaxQueue { deque<int> q,
cc; MaxQueue() { while (!q.empty()) q.pop_front(); while (!cc.empty())
cc.pop_front(); } void Insert(int x, int loc) { while (!q.empty() && q.back() <
x) q.pop_back(), cc.pop_back(); q.push_back(x); cc.push_back(loc); } int
Query(int lessloc, int op) { if (!op) { while (cc.front() < lessloc)
q.pop_front(), cc.pop_front(); return cc.front(); } else { while (cc.front() >
lessloc) q.pop_front(), cc.pop_front(); return cc.front(); } } }; inline void
swap(int &a, int &b) { int temp = a; a = b; b = temp; } inline void
SolveDown(int x, int dis) { MaxQueue q; int doubi = 1; for (int i = 1; i <= n;
i++) { if (map[i][x] == 'x') { doubi = i + 1; continue; } q.Insert(f[Old][i][x]
+ (n - i + 1), i); int loc = q.Query(max(doubi, i - dis), 0); f[New][i][x] =
f[Old][loc][x] + (i - loc); } } inline void SolveUp(int x, int dis) { MaxQueue
q; int doubi = n; for (int i = n; i >= 1; i--) { if (map[i][x] == 'x') { doubi
= i - 1; continue; } q.Insert(f[Old][i][x] + i, i); int loc =
q.Query(min(doubi, i + dis), 1); f[New][i][x] = f[Old][loc][x] + (loc - i); } }
inline void SolveRight(int x, int dis) { MaxQueue q; int doubi = 1; for (int i
= 1; i <= m; i++) { if (map[x][i] == 'x') { doubi = i + 1; continue; }
q.Insert(f[Old][x][i] + (m - i + 1), i); int loc = q.Query(max(doubi, i - dis),
0); f[New][x][i] = f[Old][x][loc] + (i - loc); } } inline void SolveLeft(int x,
int dis) { MaxQueue q; int doubi = m; for (int i = m; i >= 1; i--) { if
(map[x][i] == 'x') { doubi = i - 1; continue; } q.Insert(f[Old][x][i] + i, i);
int loc = q.Query(min(doubi, i + dis), 1); f[New][x][i] = f[Old][x][loc] + (loc
- i); } } int main() { scanf("%d%d%d%d%d", &n, &m, &startx, &starty, &k); for
(int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf(" %c", &map[i][j]);
for (int i = 1; i <= k; i++) scanf("%d%d%d", &start[i], &end[i], &dir[i]); Old
= 0, New = 1; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
f[New][i][j] = -1000000000; f[New][startx][starty] = 0; for (int i = 1; i <= k;
i++) { swap(Old, New); int tempDis = end[i] - start[i] + 1; if (dir[i] == 1 ||
dir[i] == 2) { for (int j = 1; j <= m; j++) dir[i] == 1 ? SolveUp(j, tempDis) :
SolveDown(j, tempDis); } else { for (int j = 1; j <= n; j++) dir[i] == 3 ?
SolveLeft(j, tempDis) : SolveRight(j, tempDis); } } int ans = 0; for (int i =
1; i <= n; i++) for (int j = 1; j <= m; j++) ans = max(ans, f[New][i][j]);
printf("%d\n", ans); }
Technology