相关链接
题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/07/20170623_statement.pdf
解题报告
假如我们钦定某个格子先取走靠左的三角形,那么其余格子是先取走靠左还是靠右就全部定下来了
于是我们暴力枚举一下,复杂度是$O(n^4)$
更进一步,我们发现:
假如我们钦定先取走$(x, y)$这个格子的靠左三角形
那么我们一定得先将$(x – 1, y)$这个格子的左三角形取走,然后再取走一些其他的三角形
于是同一行的信息是可以共用的,然后就可以记忆化搜索了
时间复杂度是$O(n^3)$的
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 500; const int INF = 1e7; char mp[N][N]; int n, m, ans[N]; bool up[N][N], dw[N][N], InStack[N][N], vis[N][N]; inline int read() { char c = getchar(); int ret = 0, f = 1; for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar()); for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar()); return ret * f; } inline int F(int x, int y, int t) { InStack[y][x] = 1; int nx = x + (t == 1? 1: -1), ny = y, nt = t, ret = 1; ret += vis[ny][nx]? 0: (InStack[ny][nx]? INF: F(nx, y, t)); nx = x; ny = up[y][x] == t? y - 1: y + 1; nt = up[y][x] == t? up[ny][nx]: dw[ny][nx]; ret += vis[ny][nx] || ret >= INF? 0: (InStack[ny][nx]? INF: F(nx, ny, nt)); vis[y][x] = 1; InStack[y][x] = 0; return ret > INF? INF: ret; } inline void init() { memset(vis, 0, sizeof(vis)); for (int j = 1; j <= m; j++) { vis[j][0] = 1; vis[j][n + 1] = 1; } for (int i = 1; i <= n; i++) { vis[0][i] = 1; vis[m + 1][i] = 1; } } int main() { m = read(); n = read(); for (int j = 1; j <= m; j++) { scanf("%s", mp[j] + 1); for (int i = 1; i <= n; i++) { up[j][i] = 1; dw[j][i] = 0; if (mp[j][i] == 'Z') { swap(up[j][i], dw[j][i]); } } } for (int j = 1; j <= m; j++) { init(); for (int i = n; i; i--) { ans[i] = ans[i + 1] < INF? F(i, j, 1) + ans[i + 1]: INF; } init(); for (int i = 1; i <= n; i++) { ans[i] = min(ans[i], ans[i - 1] < INF? F(i, j, 0) + ans[i - 1]: INF); printf("%d ", ans[i] >= INF? -1: ans[i] << 1); } putchar('\n'); } return 0; }