赞
踩
- //
- 问题 B: 数字游戏
- 时间限制: 1.000 Sec 内存限制: 512 MB
-
- 题目描述
- 有一天,小明给佳佳出了一道题,
- 给出一个正整数n,佳佳可以进行如下三种操作:
- 1、使n减去1
- 2、如果n是2的倍数,使n除以2
- 3、如果n是3的倍数,使n除以3
- 问佳佳最少可以通过几步操作,将n变为0。
- 为了考验佳佳的知识水平,小明给出了T个数字n1,n2,…,nT,让佳佳对每个数字都给出答案。然而佳佳一心只想着晚上吃啥,想让聪明的你来帮助他解决这个问题,并答应解决后请你吃饭,于是你义不容辞地接下了这个任务。
- 输入
- 第一行一个正整数T,表示总共有T个数字;
- 接下来T行,每行一个正整数ni
- 输出
- 共T行,每行一个数字,第i行为对于ni的答案。
- 样例输入 Copy
- 2
- 7
- 10
- 样例输出 Copy
- 4
- 4
- 提示
- 【样例解释】
- 7->6->2->1->0
- 10->9->3->1->0
-
- 【数据范围】
- 对于40%的数据,T≤10,ni≤30
- 对于70%的数据,T≤20,ni≤1000
- 对于100%的数据,T≤20,ni≤1000000

- //
- 4 -> 3 -> 1 -> 0
- 4 -> 2 -> 1 -> 0
- 5 -> 4!!! dp
- //
- #include<bits/stdc++.h>
- using namespace std;
-
- // 1<=ni<=1000000
- const int MAXN=1e6+7;
- int dp[MAXN+11]; // +11
-
- void solve()
- {
- int i;
- dp[0]=0; dp[1]=1; // init
-
- for( i=2;i<=MAXN;i++ )
- {
- dp[i]=dp[i-1]+1; // +1
- if( i%3==0 ) dp[i]=min( dp[i],dp[i/3]+1 );
- if( i%2==0 ) dp[i]=min( dp[i],dp[i/2]+1 );
- }
- }
-
- int main()
- {
- int t,n; solve();
-
- scanf("%d",&t);
- while( t-- )
- {
- scanf("%d",&n);
- printf("%d\n",dp[n]);
- }
- return 0;
- }

- //
- find:
- 01 手算模拟 发现特征 选用算法
- 02 防止越界 +11
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。