SCUT - 249 - Hello World - 数位dp
2024-08-25 00:12:40
https://scut.online/p/249
数位dp的模板题?
需要特殊判断0,这个很不优雅,因为0-1=-1是个很奇葩的东西?
#include<bits/stdc++.h>
using namespace std;
#define ll long long int a[];
ll dp[][][];//不同题目状态不同
ll dfs(int pos,int eleven,int cnt6,bool lead/*前导零*/,bool limit/*数位上界变量*/)//不是每个题都要判断前导零
{
//递归边界,最低位是0,那么pos==-1说明这个数枚举完了
if(pos==-)
return ;/*这里返回1,表示枚举的这个数是合法的,那么这里就需要在枚举时必须每一位都要满足题目条件,也就是说当前枚举到pos位,一定要保证前面已经枚举的数位是合法的。 */
//第二个就是记忆化(在此前可能不同题目还能有一些剪枝)
if(!limit && !lead && dp[pos][eleven][cnt6]!=-)
return dp[pos][eleven][cnt6];
/*常规写法都是在没有限制的条件记忆化,这里与下面记录状态对应*/
int up=limit?a[pos]:;//根据limit判断枚举的上界up;这个的例子前面用213讲过了
ll ans=;
//开始计数
for(int i=;i<=up;i++)//枚举,然后把不同情况的个数加到ans就可以了
{
int new_eleven=(eleven*+i)%;
int new_cnt6=;
if(i==)
new_cnt6=cnt6+; if(pos==&&new_eleven==)
continue;
if(new_cnt6>=){
continue;
} ans+=dfs(pos-,new_eleven,new_cnt6,lead && i==,limit && i==a[pos]);//最后两个变量传参都是这样写的
/*这里还算比较灵活,不过做几个题就觉得这里也是套路了
大概就是说,我当前数位枚举的数是i,然后根据题目的约束条件分类讨论
去计算不同情况下的个数,还有要根据state变量来保证i的合法性,比如题目
要求数位上不能有62连续出现,那么就是state就是要保存前一位pre,然后分类,
前一位如果是6那么这意味就不能是2,这里一定要保存枚举的这个数是合法*/
}
//计算完,记录状态
if(!limit && !lead) dp[pos][eleven][cnt6]=ans;
/*这里对应上面的记忆化,在一定条件下时记录,保证一致性,当然如果约束条件不需要考虑lead,这里就是lead就完全不用考虑了*/
return ans;
} ll solve(ll x)
{
//特殊处理0
if(x==)
return ; int pos=;
while(x)//把数位分解
{
a[pos++]=x%;//编号为[0,pos),注意数位边界
x/=;
} return dfs(pos-/*从最高位开始枚举*/,,,true,true);//刚开始最高位都是有限制并且有前导零的,显然比最高位还要高的一位视为0嘛
} int main()
{
memset(dp,-,sizeof(dp));
//初始化为-1 ll le,ri;
int cntcase=;
while(~scanf("%lld%lld",&le,&ri))
{
printf("Case #%d: %lld\n",cntcase++,solve(ri)-solve(le-));
}
}
最新文章
- centos执行yum出现Could not retrieve mirrorlist错误
- Python’s SQLAlchemy vs Other ORMs[转发 0]
- VB 中Sub和Function的区别
- 重置svn地址
- sql server cpu占用过高优化
- Android开发的教程和资源
- Command mvn jetty:run
- 【USACO】numtri
- TortoiseSVN期望文件系统格式在“1”到“6”之间;发现格式“7”
- mina高并发短连接导致java.io.IOException: Too many open files解决方案
- 使用gulp自动化配置环境变量
- NSString 字符串操作
- oracle HA 高可用性具体解释(之中的一个)
- Channel Allocation(DFS)
- Node.js之使用Buffer类处理二进制数据
- NOIP2011题解
- Android:ImageView控件显示图片
- 监听F5刷新,添加路由前缀
- 变量类型-Number
- python2.7安装django1.8后提示django-admin.py命令不存在
热门文章
- 【软件project】菜鸟俯瞰软件project
- Desktop Management Interface &; System Management BIOS
- Metasploit学习笔记之——情报搜集
- POJ 2586 Y2K Accounting Bug(枚举大水题)
- Domino函件收集器的配置及使用方法
- VUE 之 路由 VueRouter
- UVA - 11019 Matrix Matcher hash+KMP
- 简单的shell脚本编写
- base64 hash sha
- POJ2942 Knights of the Round Table 点双连通分量 二分图判定