【HDU 3555】Bomb

Qizy 动态规划, 数位DP, 解题报告

题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=3555

数位dp

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define LL long long
using namespace std;

const int MAXN = 30;

LL f[MAXN][MAXN][2];

inline LL read(){
	char c=getchar(); LL ret = 0;
	while (c<'0'||c>'9') c = getchar();
	while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
	return ret;
}

inline void prework(){
	for (int i=0;i<=9;i++) f[1][i][0] = 1;
	for (int k=2,tmp=0;k<=28;k++) {
		for (int i=0;i<=9;i++) {
			for (int j=0;j<=9;j++) {
				if (i == 4 && j == 9) f[k][i][1] += f[k-1][j][0];
				else f[k][i][0] += f[k-1][j][0];
				f[k][i][1] += f[k-1][j][1];
			}
		}
	}
}

inline LL cal(LL w){
	if (!w) return 0;
	else { 
		int tot = 0, arr[20]; LL ret = 0, tmp = w, t2;
		memset(arr,0,sizeof(arr));
		while (w) arr[++tot] = w % 10, w /= 10;
	
		for (int i=1;i<tot;i++) for (int j=1;j<=9;j++) ret += f[i][j][1];
		for (int i=1;i<arr[tot];i++) ret += f[tot][i][1];
		for (int i=tot-1;i;i--){
			for (int j=0;j<arr[i];j++) ret += f[i][j][1];
			if (arr[i+1] == 4 && arr[i] == 9) {
				ret += tmp%(LL)(pow(10,i-1)+0.1)+1;
				break;
			}
		}
		return ret;
	}
}

int main(){
	prework();
	int T; T = read();
	while (T--) {
		LL a=read();
		cout<<cal(a)<<endl;
	}
	return 0;
}

209 thoughts to “【HDU 3555】Bomb”

  21. Hello would you mind letting me know which webhost you’re utilizing?
    I’ve loaded your blog in 3 different web browsers and I must say
    this blog loads a lot quicker then most. Can you recommend a good web hosting
    provider at a fair price? Many thanks, I appreciate it!

    Reply

  22. I feel this is one of the such a lot vital info for me. And i’m satisfied reading your article.
    However should statement on few general issues,
    The site style is great, the articles is truly excellent : D.
    Good process, cheers

    Reply

  32. Just want to say your article is as surprising.
    The clarity in your post is just cool and i could assume you are an expert on this subject.
    Well with your permission allow me to grab your feed
    to keep up to date with forthcoming post. Thanks a million and please continue the
    enjoyable work.

    Reply

  48. Hi i am kavin, its my first occasion to commenting anyplace, when i read this
    paragraph i thought i could also create comment due to this brilliant
    piece of writing.

    Reply

  52. Magnificent website. Lots of helpful info here. I’m sending it to
    several pals ans additionally sharing in delicious. And naturally, thanks in your sweat!

    Reply

  57. Hiya very cool blog!! Man .. Beautiful .. Wonderful .. I will bookmark your site and take
    the feeds also? I’m satisfied to find a lot
    of useful information right here in the submit, we’d like work out
    more strategies in this regard, thank you for sharing. . . .
    . .

    Reply

  68. Hi! I know this is kinda off topic but I was wondering which blog platform are
    you using for this site? I’m getting fed up of WordPress because I’ve had problems with hackers and I’m looking at options for another platform.
    I would be awesome if you could point me in the direction of a
    good platform.

    Reply

  100. Ahaa, its pleasant dialogue concerning this paragraph at this
    place at this web site, I have read all that, so at this time
    me also commenting here.

    Reply

  113. Sweet blog! I found it while searching on Yahoo News. Do you
    have any tips on how to get listed in Yahoo News?
    I’ve been trying for a while but I never seem to get there!
    Appreciate it

    Reply

  127. Hi there! I just wish to offer you a huge thumbs up for your excellent info you have here on this
    post. I’ll be coming back to your web site for more
    soon.

    Reply

  141. Woah! I’m really enjoying the template/theme of this site.
    It’s simple, yet effective. A lot of times it’s very difficult to get that “perfect balance” between user friendliness and visual appeal.
    I must say you have done a superb job with this. Additionally,
    the blog loads very quick for me on Internet explorer. Outstanding Blog!

    Reply

  166. This is really interesting, You are a very skilled blogger. I have joined your feed and look forward to seeking more of your wonderful post. Also, I’ve shared your website in my social networks!

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *