HDU 4028 The time of a day（11年上海离散化DP）

题目：给出1-N这N个数，问有多少个子集，集合里的lcm是大于等于m的

可以发现m的范围是很大的，而且1-N的子集也是很多的2^N-1个。

觉得会是DP，但是由于数据范围太大，而无从下手。

其实可以发现的是虽然子集很多，但是LCM的值没有那么多，所以可以用map保存i-1个数的时候时的所有lcm值

这样就可以转移了

mapdp[i]。表示i个数，可以有it->second种情况组成it->first。

[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 110000
#define M 10005
#define N 10005
#define Min(a,b) ((a)<(b) (a):(b))
#define Max(a,b) ((a)>(b) (a):(b))
#define pb(a) push_back(a)
#define mem(a,b) memset(a,b,sizeof(a))
#define eps 1e-9
#define zero(a) fabs(a) #define LL long long
#define MOD 1000000007
using namespace std;
mapdp[45];
map::iterator it;
LL gcd(LL a,LL b){
return b==0 a:gcd(b,a%b);
}
LL lcm(LL a,LL b){
return a/gcd(a,b)*b;
}
void DP(){
dp[1][1]=1;
for(int i=2;i<=40;i++){
dp[i]=dp[i-1]; //不取第i个数的所有情况，先复制过来
dp[i][i]++; //只取第i个数，不能落下
for(it=dp[i-1].begin();it!=dp[i-1].end();it++)
dp[i][lcm(i,it->first)]+=it->second; //然后考虑在前i-1个数的基础上加入第i个数
}
}
LL n,m;
int main(){
DP();
int t,cas=0;
scanf("%d",&t);
while(t--){
scanf("%I64d%I64d",&n,&m);
LL ans=0;
//遍历一遍
for(it=dp[n].begin();it!=dp[n].end();it++)
if(it->first>=m)
ans+=it->second;
printf("Case #%d: %I64d\n",++cas,ans);
}
return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 110000
#define M 10005
#define N 10005
#define Min(a,b) ((a)<(b) (a):(b))
#define Max(a,b) ((a)>(b) (a):(b))
#define pb(a) push_back(a)
#define mem(a,b) memset(a,b,sizeof(a))
#define eps 1e-9
#define zero(a) fabs(a) #define LL long long
#define MOD 1000000007
using namespace std;
mapdp[45];
map::iterator it;
LL gcd(LL a,LL b){
return b==0 a:gcd(b,a%b);
}
LL lcm(LL a,LL b){
return a/gcd(a,b)*b;
}
void DP(){
dp[1][1]=1;
for(int i=2;i<=40;i++){
dp[i]=dp[i-1]; //不取第i个数的所有情况，先复制过来
dp[i][i]++; //只取第i个数，不能落下
for(it=dp[i-1].begin();it!=dp[i-1].end();it++)
dp[i][lcm(i,it->first)]+=it->second; //然后考虑在前i-1个数的基础上加入第i个数
}
}
LL n,m;
int main(){
DP();
int t,cas=0;
scanf("%d",&t);
while(t--){
scanf("%I64d%I64d",&n,&m);
LL ans=0;
//遍历一遍
for(it=dp[n].begin();it!=dp[n].end();it++)
if(it->first>=m)
ans+=it->second;
printf("Case #%d: %I64d\n",++cas,ans);
}
return 0;
}

HDU 4028 The time of a day（11年上海 离散化DP）