洛谷 P1679 神奇的四次方数

P1679 神奇的四次方数

题目描述

在你的帮助下，v神终于帮同学找到了最合适的大学，接下来就要通知同学了。在班级里负责联络网的是dm同学，于是v神便找到了dm同学，可dm同学正在忙于研究一道有趣的数学题，为了请dm出山，v神只好请你帮忙解决这道题了。

题目描述：将一个整数m分解为n个四次方数的和的形式，要求n最小。例如，m=706,706=5^4+3^4,则n=2。

输入输出格式

输入格式：

一行，一个整数m。

输出格式：

一行，一个整数n。

输入输出样例

输入样例#1： 

706

输出样例#1： 

2

说明

数据范围：对于30%的数据，m<=5000;对于100%的数据，m<=100,000

思路：完全背包。

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int n,ans,len;

void dfs(int tot,int num,int sum){

    if(tot==num){

        if(sum==n)    ans=tot;

        return ;

    }

    for(int i=;i<=len;i++)

        dfs(tot,num+,sum+i*i*i*i);

}

int main(){

    scanf("%d",&n);

    len=sqrt(sqrt(n))+;

    for(int i=;i<=n;i++){

        dfs(i,,);

        if(ans)    break;

    }

    cout<<ans;

}

50分暴力

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int n,len;

int f[];

int num[];

int main(){

    scanf("%d",&n);

    len=ceil(sqrt(sqrt(n))+);

    for(int i=;i<=len;i++)    num[i]=i*i*i*i;

    for(int i=;i<=n;i++)    f[i]=0x7f7f7f7f;

    for(int i=;i<=len;i++)

        for(int j=num[i];j<=n;j++)

            f[j]=min(f[j],f[j-num[i]]+);

    cout<<f[n];

}