Irelia

Irelia

逝去的是刀锋,不变的是意志

题解 P2254 【[NOI2005]瑰丽华尔兹】

posted on 2019-06-01 12:05:41 | under 题解 |

以钢琴区萌新Up主的身份来发一篇题解

模拟赛考了这道题,一开始想的暴搜,传的参数是当前点坐标和第几段区间。后来加了个记忆化,寻思能快一点,结果A了。。。

具体的话,看代码吧。

// 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;
}