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

P11816QOJ1250 Pionki 轮廓线DP

判定有解是一个比较经典的Hall定理。

也即,将 \(a\) 看作正数,将 \(b\) 看作负数,那么一个在 \((i,j,k)\)\(1\),可以与一个在 \((a,b,c)(a\ge i,b\ge j,c\ge k)\)\(-1\) 进行匹配。

根据 Hall 定理,有 \(|N(S)|\ge |S|\),转化后就是,选出一些 \(1\) 后,对所有的被其偏序的 \(-1\) 个数之和大于等于选出的 \(1\) 的个数。

那么我们在 \(N(S)\) 确定时肯定要最大化 \(|S|\),因此令 \(c_{i,j}=b_{i,j}-a_{i,j}\),问题变为对于所有的满足满足 \((a,b,c)\) 被选了,则所有 \((i,j,k)(i\le a,j\le b,k\le c)\) 的点都被选的选点方案,点权和不大于零。

转化为关于最大值的计算,考虑DP。

注意到,随着第一维 \(i\) 的增加,不妨将平面上的限制看作一条 \((m-1,0)\to (0,k-1)\) 轮廓线,那么这条线是在不断上移的(也即框住的点越来越少)。

用一个恰有 \(k\)\(1\) 的二进制数记录一条轮廓线,从 \((m-1,0)\) 开始走,遇到 \(1\) 就增加第二维,遇到 \(0\) 就减少第一维,转移就是将一对 \(01\) 改为 \(10\),这样恰好少框住一个点,于此同时再算一下本层框住点的点权和即可。

实现上,由于轮廓线是上移的过程,所以不妨维护下方没框住的点的点权和,由于全局和为零,因此改为维护答案的相反数的最小值即可。

#include<bits/stdc++.h>
using namespace std;
#define N 10505
#define int long long
int f[1<<12],g[1<<12],n,m,k,a[N][6][6];
void sol(){cin>>n>>m>>k;for(int i=0;i<n;++i)for(int j=0;j<m;++j)for(int t=0;t<k;++t)cin>>a[i][j][t];for(int i=0;i<n;++i)for(int j=0;j<m;++j)for(int t=0,x;t<k;++t)cin>>x,a[i][j][t]=x-a[i][j][t];vector<int>stu;for(int i=0;i<(1<<m+k);++i)if(__builtin_popcount(i)==k)stu.push_back(i);memset(f,0x3f,sizeof f);f[(1<<k)-1]=0;for(int i=0;i<n;++i){memset(g,0,sizeof g);for(int j:stu)if(f[j]<1e18){for(int t=1,x=m-1,y=0;t<m+k;++t){if(((j>>t)&1)==0&&((j>>t-1)&1)){//上移f[j^(3<<t-1)]=min(f[j^(3<<t-1)],f[j]);g[j^(3<<t-1)]=g[j]+a[i][x][y];}if((j>>t-1)&1)++y;else --x;}f[j]+=g[j];}}for(int i:stu)if(f[i]<0){cout<<"NIE\n";return ;}cout<<"TAK\n";
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=0;cin>>t;while(t--)sol();
}
http://www.hskmm.com/?act=detail&tid=32520

相关文章:

  • linux系统scatter/gather I/O技术
  • PostgreSQL 为什么不选择 B+ 树索引? - Lafite
  • Joeys shell
  • Redis 集群从部署到可视化管理全流程(超详细实战指南)
  • 什么是BPM流程自动化?从“财务报销”入手,一文读懂企业效率引擎
  • 软件工程学习日志2025.10.16
  • P1072 [NOIP 2009 提高组] Hankson 的趣味题
  • 25w41a快照测评:鹦鹉螺成精了?长矛教你戳穿末影人!
  • Day15-C:\Users\Lenovo\Desktop\note\code\JavaSE\Basic\src\com\classlei
  • Day14
  • window电脑开启hyperV虚拟化功能后导致本地服务端口被占用问题处理方案
  • RAG检索质量差?这5种分块策略帮你解决70%的问题
  • 初识pytorch:网络骨架中的填充之各种层
  • Day5字符型
  • 本地链路地址
  • 体育
  • Meta推出Agent Learning via Early Experience,推动语言代理自主学习新范式
  • Fiddler And LINQ - 特洛伊
  • 计算机视觉在自动化质检中的应用
  • 动态加速中优化失败路径反馈的方法
  • 铜价冲击下,如何“锁住”母排利润?
  • 前端快速开发工具推荐与实战 让开发速度提升 3 倍的完整工具链
  • js代码、js文件混淆、加密
  • Salesforce推出AI版Setup,说句话就能搞定配置?
  • 10.16读书报告
  • 火山引擎Data Agent再拓新场景,重磅推出用户研究Agent
  • 元推理:哥德尔搞不完定理,翻来覆去的搞。。。。
  • Matlab选择常见颜色
  • HyperWorks许可状态监控
  • 2025年纺丝机实力源头靠谱优质口碑厂家推荐,知名品牌纺丝机生产商哪家好?