LOJ #2733 [JOI2016]三明治 (DP)

题目链接

https://loj.ac/problem/2733

题解

神仙题……
首先可以观察到一个结论: 目标块的两块小三明治一定分别是最后和倒数第二个被吃的。
由此我们可以考虑这两块谁先被吃。这样的好处就是，起初我们一个块被吃的依赖条件是某两个块中有一个被吃就行，现在两个块中的某一个已经钦定了比它更晚，另一个就一定要比它早，这样依赖关系就形成了一张图。
那么有一个\(O(n^4)\)的做法: 对于每一个块枚举先吃哪个小三明治，然后DFS求出要先吃这个三明治需要吃掉哪些三明治。
下面还有一个结论: 设对于一个块\((x,y)\) (第\(x\)行第\(y\)列)我们先吃掉了靠左边界的块，那么对于块\((x,y-1)\) (即它左边的块)，我们也需要先吃掉靠左边界的块，右同理。
推论: 设\(L(x,y)\)是要先取走块\((x,y)\)靠左边界的块需要取走的块的集合，则\(L(x-1,y)\subset L(x,y)\).
于是枚举每一行，在这一行中从左到右DFS求\(L\), 从右往左DFS求\(R\), 遍历过的点无需再遍历。
总时间复杂度\(O(n^3)\).

代码

#include<bits/stdc++.h>
#define llong long long
#define mkpr make_pair
using namespace std;

const int N = 400;
const int INF = 1e8;
char a[N+3][N+3];
int vis[N+3][N+3];
int dp0[N+3][N+3],dp1[N+3][N+3];
int n,m;

int dfs(int x,int y,int dir)
{
    if(vis[x][y]==-1) {return INF;}
    else if(vis[x][y]==1) {return 0;}
    vis[x][y] = -1; int ret = 2;
    if(a[x][y]=='N')
    {
        if(dir==1)
        {
            if(x>1) {ret += dfs(x-1,y,a[x-1][y]=='N'?1:0);}
            if(y<m) {ret += dfs(x,y+1,1);}
        }
        else
        {
            if(x<n) {ret += dfs(x+1,y,a[x+1][y]=='N'?0:1);}
            if(y>1) {ret += dfs(x,y-1,0);}
        }
    }
    else
    {
        if(dir==1)
        {
            if(x<n) {ret += dfs(x+1,y,a[x+1][y]=='N'?0:1);}
            if(y<m) {ret += dfs(x,y+1,1);}
        }
        else
        {
            if(x>1) {ret += dfs(x-1,y,a[x-1][y]=='N'?1:0);}
            if(y>1) {ret += dfs(x,y-1,0);}
        }
    }
    if(ret<INF) {vis[x][y] = 1;}
    else ret = INF;
    return ret;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) scanf("%s",a[i]+1);
    for(int i=1; i<=n; i++)
    {
        memset(vis,0,sizeof(vis));
        for(int j=1; j<=m; j++)
        {
            dp0[i][j] = dp0[i][j-1]+dfs(i,j,0);
            if(dp0[i][j]>INF) {dp0[i][j] = INF;}
        }
        memset(vis,0,sizeof(vis));
        for(int j=m; j>=1; j--)
        {
            dp1[i][j] = dp1[i][j+1]+dfs(i,j,1);
            if(dp1[i][j]>INF) {dp1[i][j] = INF;}
        }
        for(int j=1; j<=m; j++)
        {
            int ans = min(dp0[i][j],dp1[i][j]);
            printf("%d ",ans<INF?ans:-1);
        }
        puts("");
    }
    return 0;
}

LOJ #2733 [JOI2016]三明治 (DP)

原文：https://www.cnblogs.com/suncongbo/p/11746632.html