当前位置: 首页 > news >正文

[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)\)

[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;
}
http://www.hskmm.com/?act=detail&tid=28170

相关文章:

  • MyBatis 中的动态 SQL 的相关使用方法(Javaee/MyBatis) - 教程
  • 网络优化问题
  • Java环境安装备忘录
  • 深入解析:【Spring MVC终极指南】一文掌握请求处理与响应!从Servlet原生方式到SpringMVC高效优雅写法
  • foobar2000 v2.25.2 汉化版
  • 比特币地址投毒攻击深度剖析
  • 为什么大家都爱用微擎?这几点真的太香了
  • 【JS逆向百例】某坤行 1101,雪球 1038,新 acw_sc__v2 逆向分析
  • JAVA 的模板方法模式解析
  • 《构建之法-现代软件工程》 -阅读和提问作业1
  • 计算机视觉与AI在人体成分分析中的技术突破
  • 2024-网鼎杯web-PyBlockly
  • 关于微信小程序申请地理位置接口申请
  • c++学习总结
  • 2025 年大闸蟹蟹卡 / 大闸蟹礼盒 / 大闸蟹礼券 / 好蟹汇大闸蟹选择指南:生态养殖与全国服务双保障解析
  • 分享一个超级耐玩的游戏 转载 植物大战僵尸融合版最新版(v3.0.1)支持安卓版+PC电脑版
  • 【Go 语言神器】iota 到底是什么?为什么高手都爱用它?
  • 2025 年模具生产厂家最新推荐榜单:聚焦优质源头企业,助力工程采购精准选型框格梁模具/框格梁模板/混泥土模具厂家推荐
  • 2025 年最新推荐仿石漆厂家实力厂家口碑排行榜:精选优质环保外墙内墙涂料企业权威揭晓
  • oracle查询存储过程和函数中是否包含某个字符串
  • Qoder 负责人揭秘:Qoder 产品背后的思考与未来发展
  • 2025 年半导体晶片生产厂家最新推荐榜单:专利技术与规模化供货能力双维度深度解析
  • 2025 年水产养殖降氨氮亚盐厂家最新推荐排行榜 ,助力北方对虾鱼塘螃蟹池塘养殖户轻松选购优质产品
  • CS:APP学习笔记之程序的机器级表示(三) - Invinc
  • EHOME视频平台EasyCVR构建全协议、全场景融合的视频监控中枢
  • GA/T 1400视图库平台EasyCVR平台GB28181与1400级联方式全解析
  • 2025 年玻璃钢水箱生产厂家最新推荐榜单:含 30 吨 / 订做 / 消防 / 方形 / 拼装式 / 屋顶 / 大型产品,从产能与服务双维度精选优质企业
  • linux 修改本地时区
  • crontab 定时执行python脚本失败,但手动执行却成功问题处理 - hello-*
  • 2025 年不锈钢水箱厂家最新推荐榜:优质厂家实力对比与选购指南,助您选到适配设备矩形/屋顶/定做方形不锈钢水箱厂家推荐