hdu 3555 Bomb 【数位DP】
2024-08-31 23:30:52
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3555
题意:上一题是不要62 这个是“不要49”
代码:
#include <stdio.h>
#include <ctime>
#include <math.h>
#include <limits.h>
#include <complex>
#include <string>
#include <functional>
#include <iterator>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <bitset>
#include <sstream>
#include <iomanip>
#include <fstream>
#include <iostream>
#include <ctime>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <time.h>
#include <ctype.h>
#include <string.h>
#include <assert.h>
using namespace std;
#define N 50
using namespace std;
int bit[N];
long long dp[N][3];
/*
dp[i][0]:前i位不含 49 的个数。
dp[i][1]:前i位不含 49 数且i+1位是4的个数。
dp[i][2]:前i位含 49 的个数。
*/
long long dfs(int pos, int st, bool flag)
{
if (pos == 0) return st == 2;
if (flag && dp[pos][st] != -1) return dp[pos][st];
long long ans = 0;
int u = flag ?
9 : bit[pos];
for (int d = 0;d <= u;d++)
{
if (st == 2 || (st == 1 && d == 9))
ans += dfs(pos - 1, 2, flag || d<u);
else if (d == 4)
ans += dfs(pos - 1, 1, flag || d<u);
else
ans += dfs(pos - 1, 0, flag || d<u);
}
if (flag) dp[pos][st] = ans;
return ans;
}
long long solve(long long n)
{
int len = 0;
while (n)
{
bit[++len] = n % 10;
n /= 10;
}
return dfs(len, 0, 0);
}
int main()
{
long long n;
int t;
scanf("%d",&t);
while (t--)
{
scanf("%lld", &n);
memset(dp, -1, sizeof(dp));
printf("%lld\n", solve(n));
}
return 0;
}
最新文章
- 1074, ";Column length too big for column &#39;err_solution&#39; (max = 21845); use BLOB or TEXT instead";
- JAVA发送邮件工具类
- jsp有关resquest与session和application的区别和相似性
- nginx基于域名的虚拟主机 反向代理配置实例
- 【项目相关】MVC中使用WebUploader进行图片预览上传以及编辑
- 如何在单元测试中测试异步函数,block回调这种
- Selenium firefox 版本问题
- 网易DBA私享会分享会笔记2
- 1352 - Colored Cubes (枚举方法)
- iOS 协议
- HBuilder连接IOS手机打开APP测试
- JavaWeb学习笔记八 监听器
- MAC MAMP 中安装配置使用 ThinkPHP
- jmeter循环控制器加jdbc req结果配合组合参数遍历
- orcal -对表的操作
- Session提要
- 解决org.hibernate.exception.SQLGrammarException:could not insert
- 用原生javascript写出jquery中slideUp和slideDown效果
- tinycc update VERSION to 0.9.27
- 【PAT】B1056 组合数的和(15 分)