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

[NOI2001] 炮兵阵地 - 洛谷

P2704 [NOI2001] 炮兵阵地 - 洛谷

题目大意(自己总结

给你一个01矩阵,1可以放炮兵,0不能放炮兵,每个炮兵放置之后上下左右四个方向两格不能再放置炮兵,求如何部署炮兵,让最后得到的炮兵数最多

题目主要实现思路

利用状压的性质,求出每行炮兵可能放置的位置(左右两格不能放置格外炮兵),因此可以减少枚举次数,设置dp-i-sa-sb,前i列,这一列状态为sa,前一列状态为sb可得转移方程dp-i-sa-sb = dp-i-sa-sb,dp-i-1_sb_sc+ct(sa这一行满足的炮兵数),注意第一行要初始化

#include <bits/stdc++.h>#define int long longusing namespace std;const int N = 1e6 + 10;const int mod = 1e9 + 7;int g[110][20], sta[N];int k = 0;int n, m;int dp[110][1 << 10][1 << 10]; // 第i个当前为a状态下,前一个为b状态下void pre(int i, int s){    if (i >= m)    {        sta[k++] = s;        return;    }    pre(i + 1, s);            // 不选这一位    pre(i + 3, s | (1 << i)); // 选择这一位}int cont(int i, int s){    int ans = 0;    for (int j = 0; j < m; j++)    {        if ((s >> j) & 1 && g[i][j])        {            ans++;        }    }    return ans;}void solve(){    cin >> n >> m;    for (int i = 0; i < n; i++)    {        for (int j = 0; j < m; j++)        {            char c;            cin >> c;            g[i][j] = c == 'P' ? 1 : 0;        }    }    // 预处理出每一行满足条件的结果    pre(0, 0);    for (int i = 0; i < m; i++)    {        for (int j = 0; j < k; j++)        {            int mask = sta[j];            int ct = cont(i, mask);            dp[i][mask][0] = ct;        }    }    for (int i = 1; i < n; i++)    {        for (int ja = 0; ja < k; ja++)        {            int ct = cont(i, sta[ja]);            for (int jb = 0; jb < k; jb++)            {                if (!(sta[ja] & sta[jb]))                {                    for (int jc = 0; jc < k; jc++)                    {                        if (!(sta[ja] & sta[jc]) && !(sta[jb] & sta[jc]))                        {                            dp[i][sta[ja]][sta[jb]] = max(dp[i][sta[ja]][sta[jb]], dp[i-1][sta[jb]][sta[jc]] + ct);                        }                    }                }            }        }    }    int ans = 0;    for (int i = 0; i < m; i++)    {        for (int j = 0; j < k; j++)        {            for (int l = 0; l < k; l++)            {                if (!(sta[j] & sta[l]))                {                    ans = max(ans, dp[n - 1][sta[j]][sta[l]]);                }            }        }    }    cout << ans << '\n';}signed main(){    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int T = 1;    // cin >> T;    while (T--)        solve();    return 0;}
http://www.hskmm.com/?act=detail&tid=27368

相关文章:

  • 告别 “能源黑箱”:MyEMS 如何让中小企业的能耗数据 “会说话”?
  • 实用指南:赛思金融授时服务器 从《捕风追影》纳秒困局到数字安全,赛思以全链路时钟同步方案夯实时序安全底座
  • 企业级 Java AI 开发首选!JBoltAI 带 RAG 知识库 + Agent 智能体,轻松改造老系统
  • CH585通过SPI驱动TFT屏
  • 机械手偏差,极坐标与直角坐标转换
  • 2025 年造雪机厂家最新推荐排行榜:国产优质厂家深度解析,助力滑雪场与冰雪乐园精准选购
  • 当 MyEMS 遇上数字孪生:园区能源 “透明化” 能有多极致?
  • 2025雷蒙磨粉机厂家推荐榜:定制化生产与高效研磨口碑之选
  • 技术复习要点清单
  • res-downloader v2.1.2 全平台资源下载工具深度指南:支持视频号/抖音/音视频嗅探,附常见问题解决方案
  • 从设备监控到全局调控,MyEMS 如何构建 “全链路” 能源管理体系?
  • 题解:AT_mujin_pc_2017_d Oriented Tree
  • Redis缓存穿透优化
  • 元空间的两个重要参数
  • 工作电压2.4V-5.5V*低功耗单路触摸/单键触控感应芯片VKD233HR DFN6L
  • 2025.10.9——1橙
  • 抽象函数的定义域
  • GEO优化系统哪个最好?
  • 6G多站多智能超表面(RIS)
  • 缓冲区管理
  • Oracle故障处理:ASM手动修复磁盘头
  • 智慧考试微信小程序系统:一站式在线考试解决方案
  • 深入解析:【双光相机配准】可见光相机内参标定流程
  • oracle中引号的使用总结与报错信息
  • 2025 年电线电缆厂家最新推荐:实力厂家榜单重磅发布,涵盖多品类线缆及专业选择指南国标/朝阳/低压/阻燃/耐火/北京电线电缆厂家推荐
  • 5分钟,15分钟,差距大,做5分钟线要严格止损
  • 家政服务小程序系统:一站式家政服务解决方案
  • 营销农场小程序管理系统:营销吸粉与流量变现解决方案
  • 二部图,最大权/最小权完美匹配,费用流解法
  • OIFHA251009 比赛总结