[NOI2005]瑰丽华尔兹

题目

本文无意义,仅仅是换个码风。

#include <bits/stdc++.h>
using namespace std;

const int Max = 233;

int n, m, x, y, k, ans;
int dp[2][Max][Max];
char p[Max][Max];
deque<int> que, emp;

void solve(int now, int len, int d) {
    int pre = now ^ 1;
    memset(dp[now], -63, sizeof dp[now]);
    if (d == 1) {
        for (int j = 1; j <= m; j++) {
            que = emp;
            for (int i = n; i >= 1; i--) {
                if (p[i][j] == 'x') {
                    que = emp;
                }
                else {
                    while (!que.empty() && que.back() - i > len)
                        que.pop_back();
                    while (!que.empty() && dp[pre][i][j] > dp[pre][que.front()][j] + que.front() - i)
                        que.pop_front();
                    que.push_front(i);
                    dp[now][i][j] = dp[pre][que.back()][j] + que.back() - i;
                }
            }
        }
    }
    else if (d == 2) {
        for (int j = 1; j <= m; j++) {
            que = emp;
            for (int i = 1; i <= n; i++) {
                if (p[i][j] == 'x') {
                    que = emp;
                }
                else {
                    while (!que.empty() && i - que.back() > len)
                        que.pop_back();
                    while (!que.empty() && dp[pre][i][j] > dp[pre][que.front()][j] + i - que.front())
                        que.pop_front();
                    que.push_front(i);
                    dp[now][i][j] = dp[pre][que.back()][j] + i - que.back();
                }
            }
        }
    }
    else if (d == 3) {
        for (int i = 1; i <= n; i++) {
            que = emp;
            for (int j = m; j >= 1; j--) {
                if (p[i][j] == 'x') {
                    que = emp;
                }
                else {
                    while (!que.empty() && que.back() - j > len)
                        que.pop_back();
                    while (!que.empty() && dp[pre][i][j] > dp[pre][i][que.front()] + que.front() - j)
                        que.pop_front();
                    que.push_front(j);
                    dp[now][i][j] = dp[pre][i][que.back()] + que.back() - j;
                }
            }
        }
    }
    else {
        for (int i = 1; i <= n; i++) {
            que = emp;
            for (int j = 1; j <= m; j++) {
                if (p[i][j] == 'x') {
                    que = emp;
                }
                else {
                    while (!que.empty() && j - que.back() > len)
                        que.pop_back();
                    while (!que.empty() && dp[pre][i][j] > dp[pre][i][que.front()] + j - que.front())
                        que.pop_front();
                    que.push_front(j);
                    dp[now][i][j] = dp[pre][i][que.back()] + j - que.back();
                }
            }
        }
    }
}

int main() {
    scanf("%d%d%d%d%d", &n, &m, &x, &y, &k);
    for (int i = 1; i <= n; i++)
        scanf("%s", p[i] + 1);
    memset(dp, -63, sizeof dp);
    dp[0][x][y] = 0;
    for (int i = 1; i <= k; i++) {
        int s, t, d;
        scanf("%d%d%d", &s, &t, &d);
        solve(i & 1, t - s + 1, d);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ans = max(ans, dp[k & 1][i][j]);
        }
    }
    printf("%d\n", ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注