观察一下:
- \(n\times n\) 的网格肯定每行每列都被填上了。
- 如果只保留横线,可以还原出竖线
- 只保留横线的话,因为是一个封闭图形,所以会有上半部分和下半部分,分别覆盖了上边界和下边界。
- 为了保证是凸的,上半部分一定是峰形,下半部分是谷形。
- 上半部分要在下半部分上面。
- 由于每一列都有且仅有一个竖线,所以如果考虑上半部分和下半部分中 \(1\sim i\) 列部分的末端,一定是其中一个继续延长,另一个断开成新的一条横线。
设计 DP \(f_{i, j, k,0/1,0/1}\) 表示当前考虑 \(1\sim i\) 列,上半部分横线在所有可以放横线的行中相对排名是 \(j\),下半部分的是 \(k\),且上半部分是否开始下降,下半部分是否开始上升,的方案数,因为剩余能放横线的行已经确定是 \(n - i + 2\) 个,所以不用把这一维放进状态里。
转移是容易的,枚举成新的横线的是上半部分还是下半部分,然后再枚举横线在哪里即可。
时间复杂度 \(O(n^4)\)。
[Gym-100343E]Convex Permutominoes观察一下:1. $n\times n$ 的网格肯定每行每列都被填上了。
2. 如果只保留横线,可以还原出竖线
3. 只保留横线的话,因为是一个封闭图形,所以会有上半部分和下半部分,分别覆盖了上边界和下边界。
4. 为了保证是凸的,上半部分一定是峰形,下半部分是谷形。
5. 上半部分要在下半部分上面。
6. 由于每一列都有且仅有一个竖线,所以如果考虑上半部分和下半部分中 $1\sim i$ 列部分的末端,一定是其中一个继续延长,另一个断开成新的一条横线。设计 DP $f_{i, j, k,0/1,0/1}$ 表示当前考虑 $1\sim i$ 列,上半部分横线在所有可以放横线的行中相对排名是 $j$,下半部分的是 $k$,且上半部分是否开始下降,下半部分是否开始上升,的方案数,因为剩余能放横线的行已经确定是 $n - i + 2$ 个,所以不用把这一维放进状态里。转移是容易的,枚举成新的横线的是上半部分还是下半部分,然后再枚举横线在哪里即可。时间复杂度 $O(n^4)$。```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
#define int long long
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 50 + 10, M = 1e5, mod = 998244353;int n, f[N][N][N][2][2];
int qmi(int a, int b) {int res = 1;while(b) {if(b & 1) res = res * a % mod;a = a * a % mod, b >>= 1;}return res;
}
signed main() {ios::sync_with_stdio(0), cin.tie(0); freopen("permutominoes.in", "r", stdin);freopen("permutominoes.out", "w", stdout);cin >> n;for(int i = 1; i <= n; i ++)for(int j = i + 1; j <= n; j ++)f[2][i][j][0][0] = 1;for(int i = 2; i < n; i ++) {for(int j = 1; j <= n; j ++) {for(int k = j + 1; k <= n; k ++) {for(int o1 = 0; o1 < 2; o1 ++) {for(int o2 = 0; o2 < 2; o2 ++) {int t = f[i][j][k][o1][o2];if(!t) continue;int c = n - i + 2;if(!o1) {for(int p = 1; p < j; p ++) {f[i + 1][p][k - 1][o1][o2] += t;}}for(int p = j + 1; p < k; p ++) {f[i + 1][p - 1][k - 1][1][o2] += t;}if(!o2) {for(int p = k + 1; p <= c; p ++) {f[i + 1][j][p - 1][o1][o2] += t;}}for(int p = j + 1; p < k; p ++) {f[i + 1][j][p][o1][1] += t;}}}}}}int ans = 0;for(int j = 1; j <= n; j ++) {for(int k = j + 1; k <= n; k ++) {for(int o1 = 0; o1 < 2; o1 ++) for(int o2 = 0; o2 < 2; o2 ++) if(f[n][j][k][o1][o2]) {ans += f[n][j][k][o1][o2];}}}cout << ans << '\n';return 0;
}