题解 P7239 【3D Cube】

· · 题解

这是出题人的小号，拉出来溜溜

首先是20pts的部分分。由于数据开放下载，所以手玩即可。

接下来是正解。

看到格子数很小，所以我们就可以枚举哪一些必须不能被削平（即为峰）。这一步可以用dfs解决。

然后进行dp。（类似于floyd）


    for(int k=1;k<=n*m;++k) for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){  //由于一个格子带来的收益可能会改变整个棋盘，所以需要跑n*m次 
        if(cnnt[i][j]) continue;
        else if(c[i][j]) c[i][j]=max(1,min(c[i][j],min(min(c[i-1][j],c[i][j-1]),min(c[i+1][j],c[i][j+1]))));//取min是为了最小和保证不出现额外的峰，与1取max是为了保证有 
        else c[i][j]=0;
    }

最后判断是不是满足条件即可。

details:

1.你需要满足正视图和左视图。每行每列至少有一个点不能被削掉。贪心的想每行每列只有一个点。

2.判断是否满足有点复杂难写。

总结：

最难想的是这个dp。想到了，你还得需要码力。

Code