原题请戳>>https://www.luogu.org/problem/show?pid=1679<<

题目描述

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

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

输入输出格式

输入格式：

一行，一个整数m。

输出格式：

一行，一个整数n。

输入输出样例

706

2

说明

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

****************************************************************************************************************

这题其实就是完全背包问题.而其中的物品就是i的四次方.我们首先可以确定"背包的体积"是m,且小于100000.所以我们要先早点到最大的i,且该i的四次方小于100000

通过打表可以看到17的四次方正好小于100000;所以我们直接讨论2~17的四次方共16个物品的完全背包.但是首先要对数组初始化.使a[i]=i;(即是均用1的四次方填充) 然后就套完全背包公式.代码实现如下:

#include<iostream>

using namespace std;

int a[],s[];

int sicif(int i)

{

    return i*i*i*i;

}

int min(int a,int b)

{

    return a>b?b:a;

}

int main()

{

    int i,n,j,m;

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

    {

        s[i]=sicif(i);

        //cout<<s[i]<<endl;找到大于10w的数.只需求前17个即可

    }

    cin>>m;

    for(i=;i<=m;i++) a[i]=i;//初始化

    for(i=;i<=;i++)//16个物品完全背包

    {

        for(j=s[i];j<=m;j++)

        {

            a[j]=min(a[j],a[j-s[i]]+);

        }

    }

    cout<<a[m]<<endl;

}

于是就愉快的水写完了~~