【题解】ones 唯“一”运算

【题解】ones 唯“一”运算

【题目描述】

  给定n, 计算只用1, *, +, (, ) 表示n所需要的最少的1的个数

  例子:

  3 = 1 + 1 + 1

  6 = (1 + 1 + 1) * (1 + 1)

【输入格式】

  输入为一个数n

【输出格式】

  输出所需要的最少的1的个数

【样例】

  输入:20

  输出:9

【题解】

  不难想到,使用动态规划。

  我们设dp[i](1≤i≤n)表示为表示i所需的最少的1的个数。根据定义,我们不难得出如下转移方程:

  dp[i]=min(dp[i-j]+dp[j],dp[i]);dp[i]=min(dp[i/j]+dp[j],dp[i]),i|j;

  但是考虑到较大数据,枚举i(1~n)时,如果j也从1~i枚举的话,j的枚举量都是非常的大的。因此我们观察式子,可以知道:

   对于第一个转移方程,我们根本不必考虑到i-1之前的数,因为i-1所代表的是通过i-1之前的数所能达到的最优答案。即,dp[i-a]+dp[a]的效果总是与dp[i-a-1]+dp[a+1]相同或更优。所以第一个式子完全可以优化成:dp[i]=min(dp[i-1]+1,dp[i]);

  对于第二个转移方程,j枚举到√i时即可,因为 (i/j)*j=i,再大了,也只是重复一遍j *(i/j)=i,完全没有必要。

【代码】

#include<bits/stdc++.h>

using namespace std;

const long long maxN=2000010; 
int n;
int dp[maxN]={0};

int main()
{
    memset(dp,0x7f,sizeof(dp));
    dp[0]=0,dp[1]=1;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        dp[i]=min(dp[i],dp[i-1]+1);
        for(int j=1;j<=sqrt(i)+1;j++)
            if(i%j==0)
                dp[i]=min(dp[i],dp[i/j]+dp[j]);
    }
    cout<<dp[n]<<endl;
    return 0;
}
上一篇:链表操作(创建空链表、头插法、尾插法、反转链表、修改、删除链表元素、获取链表元素位置)


下一篇:SpringCloudAlibaba 环境搭建