热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

P5694[NOI2001]探秘陨石之谜:科学与技术的交汇点

这道题目是一道富有挑战性的高维计数动态规划问题。题目背景涉及科学与技术的交汇点,旨在探讨合法括号串的生成规则。具体而言,合法括号串由三种括号(()、[]、{})组成,空串被视为合法括号串。如果\(A\)是一个不包含[]和{}的合法括号串,则\((A)\)也是合法括号串。此外,如果\(A\)和\(B\)都是合法括号串,则\(AB\)也是合法括号串。该题目不仅考验了选手对动态规划的理解,还要求他们具备较强的组合数学能力,以高效地解决复杂计数问题。

一道有趣的高维计数 DP。


题目大意

定义合法的括号串为:



  1. 仅由 (), [], {} 组成;

  2. 空串是合法括号串;

  3. \(A\) 是合法括号串且不含 [], {},则 \((A)\) 是合法括号串;

  4. \(A\) 是合法括号串且不含 {},则 \([A]\) 是合法括号串;

  5. \(A\) 是合法括号串,则 \(\{A\}\) 是合法括号串;

  6. \(A,B\) 均为合法括号串,则 \(AB\) 也是合法括号串。

定义一个括号串的深度为最大的括号嵌套数,求使用了 \(L_1,L_2,L_3\){}, [], () 且深度为 \(D\) 的合法括号串数量,答案对 \(11380\) 取模。


大体思路

由于 \(L_1\sim L_3,D\) 均不大,直接使用高维 DP,状态定义照抄题面。故定义 \(F(d,i,j,k)\) 表示使用了 \(i,j,k\) 对大、中、小括号且深度为 \(d\) 的数量。

状态转移自然是将当前串分割成两个串 \(TS\),使得 \(S\) 的深度为 \(d\),用某一种括号去套一个合法的串 \(T\)。由于嵌套一层后深度 \(\le d\),要求这个合法串 \(T\) 的深度不大于 \(d-1\)

这时,我们发现需要枚举所有 \(\le d-1\) 的深度,太过麻烦,因此对 \(F\) 做前缀和处理,即将状态定义改为 \(F(d,i,j,k)\) 表示使用了 \(i,j,k\) 对大、中、小括号且深度 \(\le d\) 的数量。

对当前串 TS,可以通过一个括号嵌套变成 (T)S[T]S{T}S。我们可以通过枚举 \(T\) 中包含多少 {}, [], (),得到状态转移方程:


\[F(d,i,j,k)=

\sum_{a=0}^{i-1}\sum_{b=0}^j\sum_{c=0}^k F(d-1,a,b,c)\times F(d,i-1-a,j-b,k-c)

\\

+\sum_{b=0}^{j-1}\sum_{c=0}^k F(d-1,0,b,c)\times F(d,i,j-1-b,k-c)

\\

+\sum_{c=0}^{k-1} F(d-1,0,0,c) \times F(d,i,j,k-1-c)

\]

特殊地,对于 \(i=j=k=0\) 时,\(F(d,0,0,0)=1\)

输出时,通过前缀和做差即可,需要特判 \(D=0\) 以及 \(L_1=L_2 = L_3 = 0\) 的情况。时间复杂度 \(O(DL^6)\)


完整代码

#include
using namespace std;
#define rep(ii,aa,bb) for(re int ii = aa; ii <= bb; ii++)
#define Rep(ii,aa,bb) for(re int ii = aa; ii >= bb; ii--)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair PII;
const ll mod = 11380;
namespace IO_ReadWrite {
#define re register
#define gg (p1 == p2 && (p2 = (p1 = _buf) + fread(_buf, 1, 1<<21, stdin), p1 == p2) ? EOF :*p1++)
char _buf[1<<21], *p1 = _buf, *p2 = _buf;
template
inline void read(T &x){
x = 0; re T f=1; re char c = gg;
while(c > 57 || c <48){if(c == '-') f = -1;c = gg;}
while(c >= 48 &&c <= 57){x = (x<<1) + (x<<3) + (c^48);c = gg;}
x *= f;return;
}
inline void ReadChar(char &c){
c = gg;
while(!isalpha(c)) c = gg;
}
template
inline void write(T x){
if(x <0) putchar('-'), x = -x;
if(x > 9) write(x/10);
putchar('0' + x % 10);
}
template
inline void writeln(T x){write(x); putchar('\n');}
}
using namespace IO_ReadWrite;
ll L1, L2, L3, D, f[35][12][12][12];
int main () {
read(L1); read(L2); read(L3); read(D);
f[0][0][0][0] = 1;
rep(d, 1, D) {
f[d][0][0][0] = 1;
rep(i, 0, L1) rep(j, 0, L2) rep(k, 0, L3) {
if(!i && !j && !k) continue;
rep(a, 0, i - 1) rep(b, 0, j) rep(c, 0, k)
(f[d][i][j][k] += f[d - 1][a][b][c] * f[d][i-1 - a][j - b][k - c]) %= mod;
rep(b, 0, j - 1) rep(c, 0, k)
(f[d][i][j][k] += f[d - 1][0][b][c] * f[d][i][j-1 - b][k - c]) %= mod;
rep(c, 0, k - 1)
(f[d][i][j][k] += f[d - 1][0][0][c] * f[d][i][j][k-1 - c]) %= mod;
}
}
if(!D) writeln(((!L1 && !L2 && !L3) ? 1 : 0));
else if(!L1 && !L2 && !L3) writeln(0);
else writeln((f[D][L1][L2][L3] - f[D - 1][L1][L2][L3] + mod) % mod);
return 0;
}


推荐阅读
  • 本文探讨了Windows 10 64位系统的实际使用体验,并与Windows 7进行了详细对比,旨在帮助用户了解两者之间的主要差异及选择合适的操作系统。 ... [详细]
  • HBase 数据复制与灾备同步策略
    本文探讨了HBase在企业级应用中的数据复制与灾备同步解决方案,包括存量数据迁移及增量数据实时同步的方法。 ... [详细]
  • 本文介绍了SIP(Session Initiation Protocol,会话发起协议)的基本概念、功能、消息格式及其实现机制。SIP是一种在IP网络上用于建立、管理和终止多媒体通信会话的应用层协议。 ... [详细]
  • 二维码的实现与应用
    本文介绍了二维码的基本概念、分类及其优缺点,并详细描述了如何使用Java编程语言结合第三方库(如ZXing和qrcode.jar)来实现二维码的生成与解析。 ... [详细]
  • 在日常生活中,支付宝已成为不可或缺的支付工具之一。本文将详细介绍如何通过支付宝实现免费提现,帮助用户更好地管理个人财务,避免不必要的手续费支出。 ... [详细]
  • 解决Win10系统显示模糊问题的方法
    Windows 10作为一款深受用户喜爱的操作系统,提供了丰富的个性化设置选项,让每位用户都能根据个人偏好定制系统界面。然而,在进行个性化设置的过程中,有时会出现显示模糊的情况,影响用户体验。本文将详细介绍如何有效解决Win10系统显示模糊的问题。 ... [详细]
  • 拨打电话时遇到‘正在通话’或无人接听的情况解析及解决方法
    当您尝试联系他人时,可能会遇到电话提示‘正在通话’或是虽然接通但无人应答的情况。本文将详细解释可能的原因,并提供相应的解决策略。 ... [详细]
  • 本文详细介绍了在Windows系统中如何配置Nginx以实现高效的缓存加速功能,包括关键的配置文件设置和示例代码。 ... [详细]
  • 如何在PyCharm中配置Python脚本的默认模板
    本文介绍如何在PyCharm中设置Python脚本的默认模板,以便每次创建新的.py文件时自动填充预设内容,提高开发效率。 ... [详细]
  • 当需要确保对象的状态在创建后不可更改时,使用记录(Record)类型是一个理想的选择。本文探讨了如何通过记录类型实现对象的不可变性,并提供了一个简单的示例来说明其用法。 ... [详细]
  • 本文详细介绍了FLV播放器的构建过程,包括如何解析FLV标签并将这些标签传递给解码器,以及如何在Qt环境中注册共享指针的信号和槽机制。 ... [详细]
  • 团支部的概念及其职能
    本文详细介绍了团支部的基本概念、组织结构以及其在共青团体系中的重要职能。 ... [详细]
  • 在开发一个网页音乐播放器时遇到问题,需要从不同源读取MP3文件的ID3标签信息,包括流派、歌手和歌曲名称等。尝试使用PHP未果后转而考虑使用JavaScript进行跨域读取,但不清楚具体配置方法,寻求技术指导。 ... [详细]
  • 探索《冯诺依曼传》:天才与时代的交响
    本文深入探讨了《冯诺依曼传》,通过分析这位20世纪杰出科学家的生平,揭示其对现代科技及理论科学的深远影响。 ... [详细]
  • 本文详细介绍了JQuery Mobile框架中特有的事件和方法,帮助开发者更好地理解和应用这些特性,提升移动Web开发的效率。 ... [详细]
author-avatar
书友56183408
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有