热门标签 | 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;
}


推荐阅读
  • 本文详细介绍了MySQL数据库服务器(mysqld)和客户端(mysql)的区别,并提供了多种启动和关闭MySQL服务器的方法。通过这些方法,您可以更好地管理和维护MySQL数据库。 ... [详细]
  • OpenGL教程四:为矢量图形添加颜色
    本文将介绍如何在OpenGL中分别为顶点和整个图形添加颜色,包括使用glColor3f函数的具体步骤。 ... [详细]
  • CRM系统最初由国外某机构提出,至今尚未形成统一的定义。本文将从多个角度探讨CRM系统的定义,并介绍其在企业中的应用。CRM系统不仅是一种技术工具,更是一种以客户为中心的商业战略。 ... [详细]
  • Spring 切面配置中的切点表达式详解
    本文介绍了如何在Spring框架中使用AspectJ风格的切面配置,详细解释了切点表达式的语法和常见示例,帮助开发者更好地理解和应用Spring AOP。 ... [详细]
  • Spring – Bean Life Cycle
    Spring – Bean Life Cycle ... [详细]
  • [c++基础]STL
    cppfig15_10.cppincludeincludeusingnamespacestd;templatevoidprintVector(constvector&integer ... [详细]
  • 双指针法在链表问题中应用广泛,能够高效解决多种经典问题,如合并两个有序链表、合并多个有序链表、查找倒数第k个节点等。本文将详细介绍这些应用场景及其解决方案。 ... [详细]
  • ZooKeeper 入门指南
    本文将详细介绍ZooKeeper的工作机制、特点、数据结构以及常见的应用场景,包括统一命名服务、统一配置管理、统一集群管理、服务器动态上下线和软负载均衡。 ... [详细]
  • 探讨Redis的最佳应用场景
    本文将深入探讨Redis在不同场景下的最佳应用,包括其优势和适用范围。 ... [详细]
  • 自动验证时页面显示问题的解决方法
    在使用自动验证功能时,页面未能正确显示错误信息。通过使用 `dump($info->getError())` 可以帮助诊断和解决问题。 ... [详细]
  • Redis 脑裂现象及其应对策略
    本文探讨了 Redis 集群中的脑裂现象及其解决方案,包括脑裂的成因、影响以及如何通过配置项防止脑裂的发生。 ... [详细]
  • 国联物流是一家由国家出资设立的国有企业,全称为湖南国联物流有限公司,成立于2001年3月,前身为株洲国联货运部。公司现办公地点位于湖南长沙,专注于大件运输、药品配送及第三方物流服务。 ... [详细]
  • Sentinel概述与应用
    本文将详细介绍Sentinel的基本概念及其在实际项目中的应用,帮助读者更好地理解和使用这一强大的流量控制工具。 ... [详细]
  • 深入解析HTML5字符集属性:charset与defaultCharset
    本文将详细介绍HTML5中新增的字符集属性charset和defaultCharset,帮助开发者更好地理解和应用这些属性,以确保网页在不同环境下的正确显示。 ... [详细]
  • 本文介绍了在 Java 编程中遇到的一个常见错误:对象无法转换为 long 类型,并提供了详细的解决方案。 ... [详细]
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社区 版权所有