BNUOJ 4359 无爱的编号(一个不错的DP )

spoiler posted @ 2011年5月08日 15:14 in 基础的dp题目 , 1655 阅读

题目大意:http://gnu.bnu.edu.cn/contest/problem_show.php?pid=4359

Description

 众所周知,拉手网有许多客户,由于客户数量实在过于庞大,因此拉手网希望为每位客户进行编号以便更好的为客户服务。每个编号为一个由 ‘0’~‘9’组成的N位数字。考虑到很多人不喜欢数字4和数字13,因此我们称包含4或包含13的编号为无爱编号,如134、84、121351都是无 爱编号,123则不是无爱编号。现在我们希望知道,所有N位的编号中,刨除掉无爱编号后剩余的编号数量。这个编号数量可能很大,我们只要知道结果的最后8 位即可。

Input

 输入的第一行是一个整数T,表示数据组数。

以下T行每行一个整数N1 N 1000000),表示编号的位数。

Output

 对于每组数据,输出一个8位整数表示编号数量的最后8位。若编号数量不足8位则用前导零填充。


题目分析: 唉,比赛的时候一个劲的往组合数学方面写,最后郁闷死掉了 ,用组合数学写,貌似太难了 ,至少我不会,没写出来,后来看了解题报告,终于 终于。。。恍然大悟 。原来是一道简单的 dp, 由于对dp 不是很敏感,所以当时没相当 状态转移方程,汗颜呐
看看题目吧:

这里我们用dp[i][0] 表示 前 i 位不包含 4与 13的编号数目 且最后一位不是1 , dp[i][1] 表示 前 i 位不包含4 与 13的 编号数目,但最后一位是1!

然后我们得到方程:

        dp[i][0] = 8*dp[i-1][0]+7*dp[i-1][1]   // 前 i -1位 合法的但最后位不为1的编号后面可以填 8个数字,(除去 1与4 因为4是
                                                                      非 法的 、dp[i][0]最后位不能为1,) ,前i-1 位合法,但最后一位是1的, 我们只能
                                                                      在其后面填 其他7个数字 得到新的合法编号(除去1 ,3, 4)

        dp[i][1]=dp[i-1][0] + dp[i-1][1];      // 这里在第i位 填1 不会构成不合法编号,所以只要把前面 i-1位的所有情况加起来就可以

                                                                  可以了   
最后一步只要

                            total[i]=dp[i][0]+dp[i][1]  就是我们要求的总的方案数,

代码:

#include<iostream>
#include<cstdio>
using namespace std;
int num[1000100][2];
int main(){
	num[0][0]=1;
	num[0][1]=0;
	for(int i=1;i<=1000000;i++){
		num[i][0]=(8*num[i-1][0]+7*num[i-1][1])%100000000;
		num[i][1]=(num[i-1][0]+num[i-1][1])%100000000;
	}
	int cas,n,ans;
	scanf("%d",&cas);
	while(cas--){
		scanf("%d",&n);
		printf("%08d\n",(num[n][0]+num[n][1])%100000000);
	}
	return 0;
}

 

Avatar_small
ldb 说:
2011年7月21日 15:17

直接对前1个初始化8 ,1不是可以吗,为什么要对num[0]进行初始化,不知道有什么用途。望解释。。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter