【题解】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;
}