题解 P2254 【[NOI2005]瑰丽华尔兹】
Ireliaღ
2019-06-01 12:05:41
~~以钢琴区萌新Up主的身份来发一篇题解~~
模拟赛考了这道题，一开始想的暴搜，传的参数是当前点坐标和第几段区间。后来加了个记忆化，寻思能快一点，结果A了。。。
具体的话，看代码吧。
```cpp
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <utility>
#include <cstring>
using namespace std;
const int MAXN = 205;
const int MAXK = 205;
const int MAXT = 4e4 + 5;
const int X[] = {0, -1, 1, 0, 0};
const int Y[] = {0, 0, 0, -1, 1};
int n, m, k, xx, yy;
int l[MAXN], r[MAXN], dir[MAXN];
char ch[MAXN][MAXN];
int dp[MAXK][MAXN][MAXN];
int Dfs(int pos, int x, int y) {//搜索
if (pos > k) return 0;//递归边界
if (dp[pos][x][y] != -1) return dp[pos][x][y];//记忆化
int len = r[pos] - l[pos] + 1;//时间段长度
int nowx = x, nowy = y;
int ret = Dfs(pos + 1, x, y);//初始化答案，即在该时间段不动
for (int i = 1; i <= len; i++) {//在时间段内一直往前推
nowx += X[dir[pos]];
nowy += Y[dir[pos]];
if (ch[nowx][nowy] == 'x') break;
if (nowx > n || nowy > m || nowx < 1 || nowy < 1) break;//判停
ret = max(ret, i + Dfs(pos + 1, nowx, nowy));
}
return dp[pos][x][y] = ret;//更新记忆化
}
int main() {
memset(dp, -1, sizeof(dp));
cin >> n >> m >> xx >> yy >> k;
for (int i = 1; i <= n; i++) {
cin >> ch[i] + 1;
}
for (int i = 1; i <= k; i++) {
cin >> l[i] >> r[i] >> dir[i];
}
cout << Dfs(1, xx, yy) << endl;
return 0;
}
```