1的个数 [EOlymp – 44]浅析

1的个数 [EOlymp – 44]浅析

一维的动态规划。
若用f(n)表示计算n所需最少1的个数,对于n=1-5的情形,f(n)=n。
举几个例子,n=6时,6=2*3,所以f(6)=f(2)+f(3)=5,对于n=9,由于9=3*3,所以f(9)=f(3)+f(3),要计算f(27),因为27=3*9,所以f(27)=f(3)+f(9),但计算f(9)还要计算f(9)=f(3)*f(3),这样计算的话会出现许多重复,刚才f(9)已经计算出来了,我们可以直接将其保存下来,将f()改为数组d[],从1开始向N计算d[i]的值即可。对于任何数字i>1,d[i]=d[i-1]+1,然后我们再检查是否有两个数字x,y相乘等于i,若有就尝试d[x]+d[y]是否小于当前d[i],若小于就更新d[i]。计算d[i]后依照此法再计算d[i+1],直到计算出d[N]. 

#include <cstdio>
#include <algorithm>
#define MAXN 5007
using std::min;


int main(void)
{
     int i,j,N;
     int dp[MAXN];
     scanf("%d",&N);
     dp[1]=1;
     for(i=2;i<=N;i++)
     {
         dp[i]=dp[i-1]+1;
         for(j=2;j*j<=i;j++)
         {
             if(i%j==0)
             {
                 dp[i]=min(dp[i],dp[i/j]+dp[j]);
             }
         }
     }

     printf("%d\n",dp[N]);

     return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注