注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1025][SCOI2009]游戏  

2014-10-20 19:41:08|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1025: [SCOI2009]游戏

想了好长时间也没想出来QAQ

写了三个版本的暴力……结果最多能跑出100+的数据

去看了题解发现ydc神犇说联赛模拟题里做过类似的Orz

NOIP滚粗预感

题解在代码下方

#include<cstdio>
#include<cstdlib>
using namespace std;
const int N = 1e3+10;
int n,m,pri[N];
short v[N];
void get(){
int nn = 1e3;
for(int i=2;i<=nn;i++){
if(!v[i])pri[++pri[0]] = i;
for(int j=1;j<=pri[0] && i*pri[j] <= nn;j++){
v[i*pri[j]] = 1;
if(i % pri[j] == 0) break;
}
}
}
long long f[N][N];
short vf[N][N];
long long F(int x=1,int left=n){
if(!left || left < pri[x])return 1;
if(vf[x][left])return f[x][left];
vf[x][left] = 1;
int tmp = pri[x];
f[x][left] += F(x+1,left);
for(int i=1;;i++){
if(tmp > left)break;
f[x][left] += F(x+1,left-tmp);
tmp *= pri[x];
}
return f[x][left];
}
int main(){
int i,j;
get();
pri[++pri[0]] = 1e9;
scanf("%d",&n);
printf("%lld",F());
return 0;
}

题解:

首先很明显是让求所有轮换长度LCM的可能个数。

然后怎么求呢?暴力很明显会T,因为n=1000的时候方案数会爆int

有这样一个贪心性质,如果每个轮换长度都是不互质的情况下如果能达到一个方案,那么互质情况下一定也能达到。

换句话说只考虑互质的时候一定是最优的。

所以根据质数的个数来DP就行了。

  评论这张
 
阅读(16)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017