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

· · 题解

这道题其实挺简单的。

首先最显然的DP： f[i][x][y] = max(f[i - 1][x'][y']) + 1;

i表示的是时间点，x和y表示位置，而x'和y'表示上一个合法位置；

当然超时（noi的题怎么可能这么水）

再看题目。注意是时间段！

那我们换种表示试试。

f[i][x][y] = max(f[i - 1][x’][y']) + dist(x,y,x',y');

i表示的是第i个时间段结束后，(x,y)这个位置最长的滑行距离。

注意(x,y)与(x',y')必定是在同一列或同一行上的，但不一定相邻。

还是超时。

那么回头再看状态转移方程，发现有要求max，而且求可能拓展的状态有线性关系（在同一列或同一行上）

单调队列！

首先按照读入的每个时间段的方向，穷举每个方向的初始点。在单调队列里记录所在列或行某一个节点减去它到这一列或行初始位置的距离。对于每个点，用步数（就是初始点到当前点的距离）加上队首。

打个比方：目前是第2短时间，向下，也就是向南。

f[1][2][2]已经求出来了，是3,并且在队首。 那么队首记录的就是3 - 2 = 1；

那么f[2][3][2] = 1 + 3 = 4；

假设f[1][2][2]还是队首；

那么f[2][4][2] = 1 + 4 = 5;

于是代码就很愉快的敲出来了。

#include <bits/stdc++.h>

using namespace std;

int n, m, x, y, k, s1, t1, d1, f[210][210][210], ans, dx[] = {0, -1, 1, 0, 0}, dy[] = {0, 0, 0, -1, 1}, q[100010], pos[100010], head, tail; 
char a[310][310];

void push(int now, int val, int x, int y){
    if (val == -0x7f7f7f7f) return ;//如果走不到这个位置 

    while (head <= tail && val - now >= q[tail])

     /*之所以要减去now是因为（x,y）这个位置不一定是在当前方向的起点上 ，所以减去now之后运算就可以方便，因为之后某一步的步数减去当前的步数得到的值就是(x,y)到之后那一步在的点的距离，这里等于化简了一下 */

        tail--;//弹出队尾 

    q[++tail] = val - now;
    pos[tail] = now;//这里记录位置，判断是不是能滑 
}

void dp(int p, int x, int y, int d, int t){

    if (t < 1) return ;//一个特判 

    head = 1; tail = 0; 
    int now = 1;

    while(x <= n && x > 0 && y <= m && y > 0){

        if (a[x][y] == 'x') head = 1, tail = 0;//如果碰到了障碍，之前做的全部失效，队列清空 
        else push(now, f[p - 1][x][y], x, y);

        while(head <= tail && now - pos[head] > t)//如果超出了能滑的区间，就可以把队首弹出去了 
            head++;

        if (head <= tail) f[p][x][y] = q[head] + now;//加上步数 
        else f[p][x][y] = -0x7f7f7f7f;

        ans = max(ans, f[p][x][y]);//记录答案 

        x += dx[d];//更新位置 
        y += dy[d];

        now++;//步数加1 
    }
}

int main(){
    ios :: sync_with_stdio(false);

    cin >> n >> m >> x >> y >> k;

    memset(f, 128, sizeof(f));

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            f[0][i][j] = -0x7f7f7f7f;

    f[0][x][y] = 0;//起始位置为滑动距离为0 

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];

    for (int i = 1; i <= k; i++){
        cin >> s1 >> t1 >> d1;
        if (d1 == 1) {
            for (int j = 1; j <= m; j++)
                dp(i, n, j, d1, t1 - s1 + 1);//这里是穷举每个方向的初始位置 
        }

        if (d1 == 2) {
            for (int j = 1; j <= m; j++)
                dp(i, 1, j, d1, t1 - s1 + 1);
        }

        if (d1 == 3) {
            for (int j = 1; j <= n; j++)
                dp(i, j, m, d1, t1 - s1 + 1);
        }

        if (d1 == 4) {
            for (int j = 1; j <= n; j++)
                dp(i, j, 1, d1, t1 - s1 + 1);
        }
    }

    cout << ans << endl;//输出答案 

    return 0;
}
//2018.2.22