从这一题开始,, 以后题目我就不贴上来了... 自己去看吧..
这一题开始肯本看不懂,, 后来是反反复复看标程看懂了..
首先要理解这么一个式子吧(算是式子吧``)
已经求出了j-1个丑数,, 现在求第j个丑数
对于每一个素数p乘以一个最小的丑数, 能使积大于第j-1个丑数
在这些乘积中寻找最小的一个即位第j个丑数.
用pindex[i]表示对于第i个素数乘以的最小丑数是多少..
/*
LANG: C
ID: zqy11001
PROG: humble
*/
#include <stdio.h>
#include <string.h>
#define MAX 100
#define getint(i) scanf("%d", &i)
#define insert(i) hum[count++] = i
long hum[1000001];
int pindex[MAX];
int prime[MAX];
int count;
int main(void)
{
int k, n;
int i;
int min, m;
freopen("humble.in", "r", stdin);
freopen("humble.out", "w", stdout);
getint(k);
getint(n);
for(i = 0; i < k; i++){
getint(prime[i]);
}
insert(1);
memset(pindex, 0, sizeof(int)*k);
while(count <= n){
min = 0x7FFFFFFF;
for(i = 0; i < k; i++){
while(prime[i] * hum[pindex[i]] <= hum[count - 1]){
pindex[i]++;
}
if(prime[i] * hum[pindex[i]] < min){
min = prime[i] * hum[pindex[i]];
m = i;
}
}
insert(min);
}
printf("%d\n", hum[n]);
return 0;
}
分享到:
相关推荐
做的很辛苦, 里面附有注释,大家支持一下吧...
本章主要衔接第二章,题目类型不定描述农民约翰被选为他们镇的镇长!他其中一个竞选承诺就是在镇上建立起互联网,并连接到所有的农场。当然,他需要你的帮助。约翰已经给他
USACO题目Palindromic Squares(回文平方数)及代码解析
usaco 合集,包括英文原题和中文译题,测试数据以及答案,很全啊!usaco 合集usaco 合集usaco 合集usaco 合集
usaco历年测试数据
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看
某些USACO题目的答案,很详细,代码清晰结构良好,算法高效易于调试
USACO题集及答案
usaco的总结和心得 包括了对题目的分了和总结 以及对题目的解法概括
USACO历年比赛测试数据:2003年 方便大家测试
USACO做题代码
USACO教程,包含USACO全部英文原题,题解(NOCOW整理版),翻译,教程,代码,测试数据。
内含USACO全部测试数据,绝对全
USACO全部译题 USACO Training Program Gateway
usaco traning的全部数据 才要3分
USACO答案,采用C++写的,题目是:name that number.
USACO1.1的源代码,新手入门可用 Only post for the new c++ students
USACO所有题目的题解 NOCOW整理版
USACO历年比赛测试数据:2006年方便大家测试
Usaco总结&题解 一位大牛写的Usaco的总结,并有所有题的题解,推荐!!