题解 【POJ1187】 陨石的秘密
2024-09-05 09:22:11
解析
考虑到数据范围,其实我们可以用记搜.
设\(f[a][b][c][d]\)表示还剩\(a\)个'{}',\(b\)个"[]",\(c\)个"()",深度\(\leq d\)个数,(注意是小于等于\(d\),这样好统计一些).
然后,回到题目.
我们可以假设当前的串由两个串组成(其中一个可能是空串),
那么根据乘法原理,当前串的方案数就等于左边的串的方案数乘上右边的串的方案数.
因此,我们可以在\(dfs\)时枚举左边的串的情况(当然右边也可以你喜欢就好).
并考虑在套最外面的是什么.
所以,若当前枚举到的是\(i\)个"()",\(j\)个"[]",\(k\)个"{}",
那么当最外面是"()"时,方案数就应是\((0,0,i-1,d-1)*(a,b,c-i,d)\)(\(a,b,c\)为\(dfs\)时的状态)
而最外面是"[]"时,就是\((0,j-1,i,d-1)*(a,b-j,c-i,d)\),
同理,最外面是"{}"时,就是\((k-1,j,i,d-1)*(a-k,b-j,c-i,d)\),
而当\(a,b,c\)都为\(0\)时,\(f[a][b][c][d]\)就为\(1\)(别忘了\(d\)是表示深度为\(0\)~\(d\)的情况数).
当\(d\)=0时,\(f[a][b][c][d]=0\).
那么,打记搜就行了(最后别忘了减掉\(f[a][b][c][d-1]\))
上代码吧:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
inline int read(){
int sum=0,f=1;char ch=getchar();
while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
return f*sum;
}
const int Mod=11380;
int f[15][15][15][35];
int la,lb,lc,ld;
int dfs(int a/*"{}"的数量*/,int b/*"[]"的数量*/,int c/*"()"的数量*/,int d){
if(!a&&!b&&!c) return f[a][b][c][d]=1;
if(d==0) return f[a][b][c][d]=0;
if(f[a][b][c][d]>=0) return f[a][b][c][d];
f[a][b][c][d]=0;
for(int i=0;i<=c;i++){
if(i) f[a][b][c][d]=(f[a][b][c][d]+dfs(0,0,i-1,d-1)*dfs(a,b,c-i,d))%Mod;//"()"在最外面
for(int j=0;j<=b;j++){
if(j) f[a][b][c][d]=(f[a][b][c][d]+dfs(0,j-1,i,d-1)*dfs(a,b-j,c-i,d))%Mod;//"[]"在最外面
for(int k=0;k<=a;k++){
if(k) f[a][b][c][d]=(f[a][b][c][d]+dfs(k-1,j,i,d-1)*dfs(a-k,b-j,c-i,d))%Mod;//"{}"在最外面
}
}
}
return f[a][b][c][d];
}
int main(){
memset(f,0xff,sizeof(f));
la=read();lb=read();lc=read();ld=read();
dfs(la,lb,lc,ld);
if(ld) dfs(la,lb,lc,ld-1);//因为小于等于d所以要减掉(d-1)的情况(就类似于前缀和)
printf("%d\n", ld?((f[la][lb][lc][ld]-f[la][lb][lc][ld-1])%Mod+Mod)%Mod:f[la][lb][lc][ld]);
return 0;
}
最新文章
- 浅谈2D游戏设计模式2- WZ文件详解(UI.WZ)之MapLogin.img(1)
- Java 枚举7种常见用法
- 关于动态URL地址设置静态形式
- oracle常用的数据迁移方法
- 浅析nginx的负载均衡
- Linux基本配置和管理 3 ---- Linux命令行文本处理工具
- 感觉差不多了。CLOUDSTACK的NAT,端口转发和防火墙结合穿透
- java中等于和equals的区别
- CSS学习笔记:利用border绘制三角形
- 新建github项目,邀请成员
- debian8下acme nginx 部署记录
- Shell 基础教程
- Redis作为lru缓存作用
- hiho 第六周 01背包
- Lerning Entity Framework 6 ------ Handling concurrency With SQL Server Database
- ANDROID DisplayManager 服务解析一
- NLP常用信息资源
- 选择合适NFC标签
- stat命令的实现-mysate 20155239吕宇轩
- Polynomial ( Arithmetic and Algebra) CGAL 4.13 -User Manual
热门文章
- vue 评论 computed watch 分隔符 局部组件 全局组件 子传父消息|父传子消息
- vue使用axios进行ajax请求
- Spring实战(十)Spring AOP应用——为方法引入新功能、为对象引入新方法
- 怎样在 Vue 中使用 v-model 处理表单?
- EXSI宿主机更换硬盘后虚机启动有问题
- PowerBI 实现不同角色看到内容不同支持动态权限管理
- 【原创】大叔经验分享(67)spring boot启动报错
- js修改当前页面地址栏参数
- Nginx作为静态资源web服务之文件读取
- Redis教程(REmote DIctionary Server)——一个高性能的key-value数据库