Sicily 1327 Pinary (SOJ 1327)「dp 动态规划」

0.00 avg. rating (0% score) - 0 votes
转载请注明: 吹水小镇 | reetsee.com
原文链接地址: http://blog.reetsee.com/archives/128

原题地址:点击打开链接

这一题能不能算DP呢,其实只是一个简单的迭代,不过也可以说是DP。

初看这条题我是没有什么想法,思路比较乱,但是想到了状态转移之后就豁然开朗。

——————正文——————

这题的时间卡的比较紧,数据规模最大有9*10^7,而1s大概就允许复杂度为10^8左右,所以比较高效的算法才能够AC

假设f[i]表示当结果的位数为i时,i为所能表示的所有数字的数量,即便当i为3时,f[i]=2,因为有100和101

这样就比较容易得到递推公式:f[i]=f[i-2]+f[i-1]+…+f[2]+f[1]+1

这是因为对于i位数,其总共的情况数就等于——(左数起)第2位到第j-1位都为0,第j位为1的时候——所有的情况数之和。

同时我们发现,计算f[i-1]时,有f[i-1]=f[i-3]+f[i-4]+…+f[1]+1,计算f[i]时,有f[i]=f[i-2]+f[i-3]+…+f[1]+1,等式的右边被重复计算,于是我们使用一个变量sum[i]来保存f[1]+…+f[i]的值

这样就有以下表达式:

f[1]=f[2]=1;

sum[1]=1; sum[2]=2;

f[i]=sum[i-2]+1;

sum[i]=sum[i-1]+f[i] => sum[i]=sum[i-1]+sum[i-2]+1;

因此发现根本不需要计算f[i],因此最终的代码里面直接使用sum就可以了。

计算得到sum之后,从sum[i]我们就知道了有i位及以下位数的数字其总共可以表达的数有多少个。

根据这个,我们对于每一个输入tmp,都不断查找刚好超过当前tmp的sum[i],这样就表示最终的结果在i位必定是1,然后tmp减去sum[i-1]+1(思考一下为什么呢?),再重复本句的步骤即可,知道了所有1的位置,那就知道了最终的结果。

代码非常短,如下:

//f[i]=f[i-2]+f[i-3]...+f[1]+1
#include<iostream>
#include<stdio.h>
#include<memory.h>
#include<cstring>
//long long f[63];
long long sum[45];
long long tmp=1;
int b[1000];
int n;
void compute()
{
	memset(b,0,sizeof(b));
	int i,maxi=0,bound=40;
	while(tmp!=0)
	{
	  i=1;
	  for(;i<=bound && sum[i]<tmp;i++)
	  {}
	  maxi=(maxi>i)?maxi:i;
	  b[i]=1;
	  tmp-=sum[i-1]+1;
	  bound=i-2;
	}

	for(i=maxi;i>=1;i--)
	  printf("%d",b[i]);
	printf("\n");
}
int main()
{
	//freopen("in","r",stdin);
	//freopen("out","w",stdout);
	//f[0]=0; f[1]=f[2]=1;
	sum[1]=1; sum[2]=2;
	for(int i=3;i<=40;++i)
		sum[i]=sum[i-1]+sum[i-2]+1;
	scanf("%d",&n);
	while(n--)
	{
		scanf("%lld",&tmp);
		compute();
	}
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注