POJ3208魔鬼数
2024-09-21 16:38:36
题目:http://poj.org/problem?id=3208
与一般的数位dp有点不同的是,没有给出上界,而是要通过值来判断这一位该填什么。
当然是从高位向低位填。
为了知道这一位填下去对答案有什么影响,需要预处理出后面无限制的魔鬼数个数。
预处理魔鬼数最重要的是不重不漏。这一位的魔鬼数=上一位的所有魔鬼数+这一位填6带来的新魔鬼数。
新魔鬼数不能与上一位已有的魔鬼数重复,所以需要记录“开头有2个6的非魔鬼数”。
为了得到这个,递推需要记录“开头有1个6的非魔鬼数”和“开头有0个6的非魔鬼数”。
f [ i ][ 0 ]=9*f [ i-1 ][ 0 ]+9*f [ i-1 ][ 1 ]+9*f [ i-1 ][ 2 ]; //不填6
f [ i ][ 1 ]=f [ i-1 ][ 0 ]; f [ i ][ 2 ]=f [ i-1 ][ 1 ]; f [ i ][ 3 ]=f [ i-1 ][ 2 ]; //填6
代码中n-=cnt意思是这一位越过这个j之后,当前累计魔鬼数数量就多了cnt个。就像普通数位dp一样。
看了蓝皮书上的精美写法!竟然可以用一句for给m赋值!l 的循环也写的很好!
dp的初值是自己不熟的地方。
别忘了输出当前位之后要break。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int LM=;
int n,m,k,t;
long long f[LM+][];
void pre()
{
f[][]=;//
for(int i=;i<LM;i++)
{
for(int j=;j<;j++)
{
f[i+][j+]+=f[i][j];
f[i+][]+=*f[i][j];
}
f[i+][]+=*f[i][];
}
}
int main()
{
pre();
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
k=;
for(m=;f[m][]<n;m++);
for(int i=m;i;i--)//i
for(int j=;j<=;j++)
{
long long cnt=f[i-][];
if(j==||k==)
for(int l=max(-k-(j==),);l<;l++)
cnt+=f[i-][l];
// printf("i=%d j=%d cnt=%lld n=%d\n",i,j,cnt,n);
if(cnt<n)n-=cnt;
else
{
if(k<)
{
if(j==)k++;
else k=;
}
printf("%d",j);
// printf("i=%d j=%d\n",i,j);
break;
}
}
printf("\n");
}
return ;
}
最新文章
- 有史来最大改变 Android 5.0十大新特性
- activity传值到fragment
- SQL Server 系统表简介
- CODESOFT中怎样打印数据库中的特定数据?
- JS增删改HTML表格
- WPF 控件截图位置不正确的问题
- 用js实现选项卡切换效果
- 【原创】Linux下获取命令的帮助与常用命令
- http server v0.1_http_webapp.c
- 分享29个超赞的响应式Web设计
- 官网的许多Mobile开发教程,Blog和示例代码
- 高级UIKit-10(UDPSocket)
- 64位与32位编程的数据类型区别(C/C++)
- string,stringbuilder和stringbuffer的区别
- 在Magento 2中创建管理员菜单
- github隐藏文件&;删除文件
- vs中添加库文件WinMM.Lib
- module &#39;sign.views&#39; has no attribute &#39;search_name&#39;
- 一个是EF内联多表查询,一个是EF中写SQL文。
- matlab与python读取tiff文件