首页 > ACM题库 > HDU-杭电 > HDU 4028-The time of a day-动态规划-[解题报告]HOJ
2015
04-15

HDU 4028-The time of a day-动态规划-[解题报告]HOJ

The time of a day

问题描述 :

There are no days and nights on byte island, so the residents here can hardly determine the length of a single day. Fortunately, they have invented a clock with several pointers. They have N pointers which can move round the clock. Every pointer ticks once per second, and the i-th pointer move to the starting position after i times of ticks. The wise of the byte island decide to define a day as the time interval between the initial time and the first time when all the pointers moves to the position exactly the same as the initial time.
The wise of the island decide to choose some of the N pointers to make the length of the day greater or equal to M. They want to know how many different ways there are to make it possible.

输入:

There are a lot of test cases. The first line of input contains exactly one integer, indicating the number of test cases.
  For each test cases, there are only one line contains two integers N and M, indicating the number of pointers and the lower bound for seconds of a day M. (1 <= N <= 40, 1 <= M <= 263-1)

输出:

There are a lot of test cases. The first line of input contains exactly one integer, indicating the number of test cases.
  For each test cases, there are only one line contains two integers N and M, indicating the number of pointers and the lower bound for seconds of a day M. (1 <= N <= 40, 1 <= M <= 263-1)

样例输入:

3
5 5
10 1
10 128

样例输出:

Case #1: 22
Case #2: 1023
Case #3: 586

题目:http://acm.hdu.edu.cn/showproblem.php?pid=4028

线性离散化DP。。。表示不会。。如果直接用数组存放会爆掉内存的。。所以用map。

DP[i][j]是以第i个指针为结束的最小公倍数j的方案数。

typedef    map<LL,LL>mp;     第一个表示第i个指针为结束的最小公倍数j,第二个为以第i个指针为结束的最小公倍数j的方案数

下面是AC代码:

#include<iostream>
#include<map>
using namespace std;

#define LL __int64 
LL m;
int n;
typedef map<LL,LL> mp;
mp dp[45];                        //离散化DP,DP[i][j]是以第i个指针为结束的最小公倍数j的方案数。

LL gcd(LL a,LL b){
	return b==0?a:gcd(b,a%b);
}

LL lcm(LL a, LL b){
	return a*b/gcd(a,b);
}
void DP(){
	int i;
	dp[1][1]=1;
	
	for(i=2;i<=40;i++){
		dp[i]=dp[i-1];
		dp[i][i]+=1;
		
		for(mp::iterator it=dp[i-1].begin();it!=dp[i-1].end();it++){
			LL t=lcm(it->first,i);
			
			dp[i][t]+=it->second;
		}
		
	}
	
	
}

int main()
{
	int T,t;
	DP();
	scanf("%d",&T);
	for(t=1;t<=T;t++)
	{
		scanf("%d%I64d",&n,&m);
		printf("Case #%d: ",t);
		LL ans=0;
		for(mp::iterator i=dp[n].begin();i!=dp[n].end();i++)
			if(i->first>=m)ans+=i->second;
			printf("%I64d\n",ans);
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/w00w12l/article/details/7743615


  1. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  2. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.