[BZOJ 1499] 瑰丽华尔兹

Link:https://www.lydsy.com/JudgeOnline/problem.php?id=1499

Solution :

能立即发现这是和动态规划相关的题目

令f[t][i][j]表示第t段时间时，钢琴位于(i,j)处时，从第1段时间到第t段时间的最长滑行路程。

f[t][i][j]=max{ f[t−1][i last][j last] + dist{ (i last,j last) , (i,j) } }

由于四个方向的处理类似，这里以向右举例：

f[t][i][j]=max{ f[t−1][i][j′] + (j−j′) }=j+max{f[t−1][i][j′]−j′} , j−j′≤end-start+1

对于每个f[t][i][j]，我们就是找到最大的max{f[t−1][i][j′]−j′}，同时使得j−j′≤end-start+1

由于j-j'单调递减，每次需要弹出队首元素，我们使用单调队列而非单调栈来维护这个序列

 

Code：

#include <bits/stdc++.h>

using namespace std;

const int MAXN=;

const int INF=<<;

inline int read()

{

    char ch;int num,f=;

    while(!isdigit(ch=getchar())) f|=(ch=='-');

    num=ch-'';

    while(isdigit(ch=getchar())) num=num*+ch-'';

    return f?-num:num;

}

int n,m,X,Y,k,dp[][MAXN][MAXN],d=;  //滚动数组优化

char dat[MAXN][MAXN];

int st,end,dir,res=,que[MAXN],t[MAXN];

int dx[]={,-,,,},dy[]={,,,-,};

void solve(int x,int y)

{

    int l=,r=,now=;

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

    {

        if(dat[x][y]=='x') l=,r=;

        while(l<=r && now-t[l]>end-st+) l++;  //弹出队首

        while(l<=r && que[r]<dp[d^][x][y]-now) r--;  //保证递减的单调性

        que[++r]=dp[d^][x][y]-now;t[r]=now;

        dp[d][x][y]=que[l]+now;

        res=max(res,dp[d][x][y]);now++;

        x+=dx[dir];y+=dy[dir];

    }

}

int main()

{

    cin >> n >> m >> X >> Y >> k;

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++)

            cin >> dat[i][j];

    memset(dp,0x80,sizeof(dp));

    dp[][X][Y]=;

    for(int i=;i<=k;i++)

    {

        st=read(),end=read(),dir=read();

        d^=;

        if(dir==)

            for(int i=;i<=m;i++) solve(n,i);

        else if(dir==)

            for(int i=;i<=m;i++) solve(,i);

        else if(dir==)

            for(int i=;i<=n;i++) solve(i,m);

        else

            for(int i=;i<=n;i++) solve(i,);

    }

    cout << res;

    return ;

}

Review:

1、对于有决策单调性的DP，

考虑利用其单调性优化（斜率优化，单调栈，单调队列）

 

同时注意考虑限制条件，判断何时弹出队首

 

2、如果DP的数组每一层只用一次，使用滚动数组优化空间