拿糖果问题
问题描述 妈妈给小B买了N块糖!但是她不允许小B直接吃掉。 假设当前有M块糖,小B每次可以拿P块糖,其中P是M的一个不大于根号下M的质因数。这时,妈妈就会在小B拿了P块糖以后再从糖堆里拿走P块糖。然后小B就可以接着拿糖。 现在小B希望知道最多可以拿多少糖。 输入格式 一个整数N 输出格式 最多可以拿多少糖 样例输入 15 样例输出 6 数据规模和约定 N <= 100000
解题思路: 这道题关键在于数字P,首先理解数字P,它有三个条件,其一是质数,其二是M的一个因数,其三要小于根号下M。 接下来看问题,问的是 希望知道最多可以拿多少糖,而拿糖呢 是 有N颗糖拿最多的糖 看到这个熟悉的架构了吗,这表明,从N中拿最多的糖建立在从N-1到1中拿最多的糖的解上,而我们知道,动态规划问题的一个要点在于,整体的最优解,一定建立或包含在子最优解上的,也就说从M中挑选P的最优解,一定建立在从M'中挑选P'的最优解上。通俗的讲,假设有N = 15,我现在已经知道了N = 1 ,2 ,3 。。。14的答案,首先当N = 15时,它的质因数为2或者3.也就是说,我如果拿2颗,那么还剩15 - 2 * 2 = 11颗,而我已经知道了11颗糖的时候我能拿的最多糖果的答案,那么N = 15时,我能拿到的糖果就是当糖果还有11颗是我能拿的数量加上我已经拿的2颗。同理,还要考虑质因数为3的情况,两种情况中那个情况最优,则答案就是那个。 所以我们可以得出递推式: dp[i] = dp[i - 2 * prime] + prime 其中,i代表当前的糖果数量,dp[i]的值为当糖果数量为I时我能拿的最多的糖果。 当然,我们这个递推式还不完整,还漏了一点。就是会有多个质因数可以供选择,我们必须对于每个质因数都计算一次,然后选其中最大的情况,所以,完善后的递推式为 dp[i] = max( dp[i],dp[i - 2 * prime] + prime ) 当所有准备工作完成后,我们可以开始了
?
c++代码:
?
#include <iostream>
#include <vector>
#include <cmath>
using std::cout;
std::cin;
std::vector;
std::max;
int main()
{
vector<int> prime;
//存放小于等于根号下 number 的所有质数
int number; 等待输入的总糖果数量
bool flag; 状态。判断一个数字是不是质数
cin>>number;
vector<int> dp(number + 1,0); dp向量。记录当糖果数量为i时能拿的糖果
求质数,并将所有质数保存到prime中
int sqt1 = sqrt(number);
for(int i = 2; i <= sqt1; ++i)
{
int sqt2 = sqrt(i);
flag = true;
int j = 2; j <= sqt2; ++j)
{
if(i % j == 0)
flag = false;
}
if(flag == )
prime.push_back(i);
}
处理dp向量
1; i != number + 1; ++i) i代表dp的下标,代表糖果的数量
{
sqrt(i);
int _size = prime.size();
0; j != _size; ++j) 遍历整个质数的数组
{
if(prime[j] <= sqt2 && i % prime[j] == 0) 如果这个质数小于等于根号下当前糖果的数量 且 是它的因数的话
{
dp[i] = max(dp[i],dp[i - 2 * prime[j]] + prime[j]); 求最优解
}
}
}
cout<<dp[number];
return ;
}
?
c++代码:
#include <iostream> #include <vector> #include <cmath>
using std::cout; using std::cin; using std::vector; using std::max;
int main() { vector<int> prime; //存放小于等于根号下 number 的所有质数 int number; //等待输入的总糖果数量 bool flag; //状态。判断一个数字是不是质数
cin>>number; vector<int> dp(number + 1,0); //dp向量。记录当糖果数量为i时能拿的糖果
//求质数,并将所有质数保存到prime中 int sqt1 = sqrt(number); for(int i = 2; i <= sqt1; ++i) { int sqt2 = sqrt(i); flag = true; for(int j = 2; j <= sqt2; ++j) { if(i % j == 0) flag = false; } if(flag == true) prime.push_back(i);
}
//处理dp向量 for(int i = 1; i != number + 1; ++i) //i代表dp的下标,代表糖果的数量 { int sqt2 = sqrt(i); int _size = prime.size(); for(int j = 0; j != _size; ++j) //遍历整个质数的数组 { if(prime[j] <= sqt2 && i % prime[j] == 0) //如果这个质数小于等于根号下当前糖果的数量 且 是它的因数的话 { dp[i] = max(dp[i],dp[i - 2 * prime[j]] + prime[j]); //求最优解 } } }
cout<<dp[number]; return 0; }
? (编辑:李大同)
【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!
|