Number String(HDU 4055,动态规划递推,前缀和优化)
2024-09-08 16:26:42
点击加号查看代码
#include<bits/stdc++.h>//前缀和优化版本,不易理解
using namespace std;
#define ll long long
const ll maxn=;
const ll mod=;
ll sum[maxn][maxn];
ll dp[maxn][maxn];
char str[maxn]; int main()
{
str[]='*';
str[]='*';
scanf("%s",str+);
ll len=strlen(str)-;
sum[][]=;
dp[][]=;
for(ll i=;i<=len;i++)
for(ll j=;j<=i;j++)
{
if(str[i]=='I'||str[i]=='?')
{
dp[i][j]=(dp[i][j]+sum[i-][j-])%mod;
}
if(str[i]=='D'||str[i]=='?')
{
ll temp=((sum[i-][i-]-sum[i-][j-])%mod+mod)%mod;
dp[i][j]=(dp[i][j]+temp)%mod;
}
sum[i][j]=(dp[i][j]+sum[i][j-])%mod;
}
cout<<sum[len][len]<<endl;
}
前缀和优化版本,不易理解
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=;
const ll mod=;
ll dp[maxn][maxn];
char str[maxn]; int main()
{
str[]='*';
str[]='*';
scanf("%s",str+);
ll len=strlen(str)-;
dp[][]=;
for(ll i=;i<=len;i++)
for(ll j=;j<=i;j++)
{
if(str[i]=='I')
{
for(ll k=;k<j;k++)
{
dp[i][j]+=dp[i-][k]%mod;
}
}
else if(str[i]=='D')
{
for(ll k=j;k<i;k++)
{
dp[i][j]+=dp[i-][k]%mod;
}
}
else
{
for(ll k=;k<=i;k++)
{
dp[i][j]+=dp[i-][k]%mod;
}
}
}
ll ans=;
for(ll i=;i<=len;i++)
{
ans+=dp[len][i]%mod;
}
cout<<ans<<endl;
// for(int i=1;i<=len;i++)//测验每一个dp是否符合预期
// for(int j=1;j<=len;j++)
// {
// printf("%d ",dp[i][j]);
// if(j==len)
// printf("\n");
// }
}
超时版本,但是容易理解
思路用图表示
首先感谢糖栗子的博文http://www.cnblogs.com/tanglizi/p/9471078.html以及他的热心帮助
下面上图:
最新文章
- xcode6 beta 中智能提示(自动完成)功能有时不显示的问题
- Java中 NIO与IO的区别
- GitHub安装配置
- RHEL6.5及Win7的和谐共处(投机版)
- ABAP 内表的行列转换-发货通知单2
- 介绍开源的.net通信框架NetworkComms框架之六 x509证书通信
- Access 中数据库操作时提示from子句语法错误
- 关于uboot中tftp上传内存数据到tftp服务器
- C# 对Excel文档打印时的页面设置
- tomcat启动很慢的原因
- UVa 1393 (容斥原理、GCD) Highways
- WebRTC clientICE 延迟问题
- Zookeeper ZAB 协议分析
- Unity3d的模型自动导入帧数表
- OSPF 高级实验
- Java:配置环境(Mac)——MySQL
- Centos 7 图形安装笔记(超详细)
- ES - es为什么要移除type?
- xvfb-run: error: xauth command not found 解决方式
- JQuery快速入门-事件与效果
热门文章
- 【bzoj2600】 [Ioi2011]ricehub
- iOS10 国行iPhone联网权限问题处理
- 牛客网9.9比赛 C 保护
- POJ2127 Greatest Common Increasing Subsequence
- libnids 中哈希表的建立
- [App Store Connect帮助]六、测试 Beta 版本(4.1) 管理 Beta 版构建版本:为构建版本添加测试员
- JavaScript--DOM节点属性
- HDU 4135 容斥原理
- 使用wkwebview后,页面返回不刷新的问题
- HTML基础2——综合案例2——复杂的嵌套列表