本文主要是介绍NYOJ 708 ones，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
OJ题目 ：http://acm.nyist.net/JudgeOnline/problem.php?pid=708
描述
- 输入
- There are multiple test cases. Each case contains only one line containing a integer N 输出
- For each case, output the minimal number of 1s you need to get N. 样例输入
-
2 10
样例输出 -
2 7
状态转换方程：a[n]=min(a[k]+a[n-k], a[t]+a[n/t])
int main() {int n,ans;int dp[10002];memset(dp,0,sizeof(dp));dp[1] = 1;int b,e;for(int i = 2;i <= 10000;i++){b = 1;e = i - 1;int m = i;while(b <= e){m = Min(m , dp[b] + dp[e]);b++;e--;}b = 2;e = i/2;while(b <= e){if(i%b == 0){e = i/b;m = Min(m,dp[b] + dp[e]);}b++;}dp[i] = m;}while(scanf("%d",&n) != EOF){printf("%d\n",dp[n]);}return 0; }
这篇关于NYOJ 708 ones的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
