HDU Simple Addition Expression 例题

HDU Simple Addition Expression 题解

给出一个数N，求小于这个数的一个数i 是的i + (i+1) + (i+2)中每个数位相加都没有进位。

原题：http://acm.hdu.edu.cn/showproblem.php?pid=2451

使用动态规划法是不难的。等于是有两条探索路径的动态规划法问题，初级动态规划就能搞定了，这里不讲了。

要学好数学，所以这里使用组合数学求解，但是很麻烦的就是如何思考计算。

关键是如何分情况。

原来这里把最高位的最大值分开，而不是分开最小值（0）的情况计算比较方便。

下面看221这个数的计算过程：

HDU Simple Addition Expression 例题

逐位计算，最高位计算的时候，是考虑不选择最大数的时候，等到下一位的时候才考虑选择了最大数的时候。

如何看图：

First bit的时候：

每位中可以有多少个数字选择就相乘，比如上图2下面有0和1 共2个选择，2下面有0,1,2,3共4个选择，1下面有0,1,2共3个选择，那么就有2*4*3= 24个选择了

Second bit的时候：

1 * 2 * 3 = 6个选择

Third bit的时候：

1*1*1 = 1个选择。

所以N=221的时候，答案是24+6+1 = 31个选择。

一步小心就会计算重复，答案出错的。

还有注意计算251这个数的时候：

HDU Simple Addition Expression 例题

到了第2位的时候，因为最高位只能选择到3了，所以不用计算第三位的情况了，直接跳出就可以。

最高位的最大值和非最大值就这样巧妙地分开处理了。

#include <stdio.h>
#include <cmath>
#include <string.h>

class SimpleAdditionExpression2451_2
{
public:
	SimpleAdditionExpression2451_2()
	{
		char str[11];
		while (scanf("%s", str) != EOF)
		{
			long long ans = 0;
			int len = strlen(str);
			for (int i = 0; i < len; i++)
			{
				if (i+1 == len)
				{
					if (str[i] >= '3')
						ans += 3;
					else ans += str[i] - '0';
				}
				else
				{
					if (str[i] > '3')
					{
						ans += (int)pow(4.0, len-i-1)*3LL;
						break;
					}
					ans += (int)pow(4.0, len-2-i)*3*(str[i]-'0');
				}
			}
			printf("%I64d\n",ans);  
		}
	}
};

数学思维还是十分困难的。

一开始，自己写了个比较乱的程序，分情况没分好，思维没组织好，导致程序写的不够简洁。

然后参考了这位仁兄的程序：http://blog.csdn.net/ooooooooe/article/details/17121541

整理一下程序就变得十分整洁了。

HDU Simple Addition Expression 例题

相关推荐