题目描述
Miss Cat wants to draw a picture as a present for Mr. Dog's birthday. Knowing bones are dogs' favorite, Miss Cat decides to draw some bones. Since it's Mr. Dog's N-th birthday, N identical bones are needed. To complete this task, Miss Cat can do one of the four following operations every time.
(1) Draw: draw a single bone.
(2) Delete: delete a single bone that has already existed.
(3) Copy: copy all the existing bones to the clipboard.
(4) Paste: paste clipboard contents to current picture.
Please note that the content in clipboard changes only after you perform a copy operation. In the beginning, both the picture and the clipboard are empty.
Now, Miss Cat wants to complete the picture as soon as possible. Please help her to calculate how many operations she needs at least.
输入格式
Input file consists of multiple test cases, ended by EOF. Every case contains only one integer N(0<N≤2000) . The number of test cases will not exceed 2000.
输出格式
Output one line containing the answer for every case.
输入样例
2
4
6输出样例
2
4
5数据不大, 显然可以打大小为2000的表来完成.
下面是毫无技术含量的暴力打表.
话说最近single number的AC率提高显著啊233 是什么原因我也很好奇啊
/*
USER_ID: test#birdstorm
PROBLEM: 189
SUBMISSION_TIME: 2014-03-18 02:01:44
*/
#include <stdio.h>
#define For(i,m,n) for(i=(m);i<(n);i++)
#define MIN(x,y) (x)<(y)?(x):(y)
#define MAXN 2005int cnt[MAXN];int calc(int x)
{int i, add, mult, smaller, min = x;For(i,1,x) {add = x - i;mult = x % i == 0 ? x / i : ((x / i + 1) * i - x) + (x / i + 1);smaller = MIN(mult, add);min = MIN(min, smaller + cnt[i]);}cnt[x] = min;
}main()
{int i, j, n, x;cnt[1] = 1;For(i,2,2001) calc(i);while(scanf("%d",&x)!=EOF) printf("%d\n",cnt[x]);return 0;
}