首页 > 代码库 > nyoj 708 ones 动态规划
nyoj 708 ones 动态规划
http://acm.nyist.net/JudgeOnline/problem.php?pid=708
状态转移方程的思路:对于一个数N,可以是N - 1的状态+1 得到,另外,也可以是(n / 2) * (1 + 1)得到,同理对于任意的奇数p,都有如果n可以整除p,都有f(n / p) + f(p)
?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | #include<stdio.h> int dp[10010]; bool isprime[101]; int prime[101]; int total; void sol() { int i; for (i = 4; i < 10010; i++) { int min = dp[i - 1] + 1; int j; for (j = 0; prime[j] < i && j < total; j ++) { if (i % prime[j] == 0) { min = min < (dp[i / prime[j]] + dp[prime[j]]) ? min : dp[i / prime[j]] + dp[prime[j]]; } } dp[i] = min; } } int main() { int n; dp[1] = 1; dp[2] = 2; dp[3] = 3; int i, j; for (i = 2; i * i < 100; i++) { if (isprime[i] == 0) { for (j = i + i; j < 100; j+= i) { isprime[j] = 1; } } } for (i = 2; i < 100; i++) { if (isprime[i] == 0) prime[total ++] = i; } sol(); while ( scanf ( "%d" ,&n) != EOF) { printf ( "%d\n" , dp[n]); } return 0; } |
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。