当前位置：首页 > news >正文

P1679 神奇的四次方数

news 来源：原创 2024/5/20 3:48:02

P1679 神奇的四次方数

题目描述

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

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

输入输出格式

输入格式：

一行，一个整数m。

输出格式：

一行，一个整数n。

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

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

由记忆化递归的参数推出DP的状态及状态转移方程

完全背包问题

洛谷题解：

这道题目我们使用背包问题的思想来做。

这里，我们先把每一个四次方数打表。打到什么位置呢？

通过简单的推理，我们发现，只要打到 $\sqrt[4]{m}4m的4次方就够了。$

为什么呢？因为为了凑出这个数，我们肯定用比他小的数来凑，如果超过了 $\sqrt[4]{m}4m，就不可能用上了。$

因此我们也可以用楼下的方法，打表打到18，因为 ${18}^{4}184已经超过了max(m)={10}^{5}max(m)=105。$

然后，以每一个四次方数为体积，1为物品重量，做完全背包（压维）。

特殊在于，f数组初始化为Inf.初值设置 $f_0=0f0=0，那么最终的结论就是f_mfm。$

代码：

（其实这篇题解最重要的是下面这个部分）。

Extra：若把四方数改为平方数，那么做法也是一样的；

不过这时有一个定理，叫拉格朗日四方和定理。有兴趣的同学可以自行查阅。

它的大概意思就是，任何自然数都可以表示为n个平方数之和（n<=4）。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #define min(x,y) (x<y?x:y)
 5 const int MAXN=200010;
 6 int s[MAXN],f[MAXN];
 7 int m;
 8 
 9 int main()
10 {
11     scanf("%d",&m);
12     for(int i=1;i<=m;i++)
13         f[i]=1e8;
14     int n=ceil(sqrt(sqrt(m))+1);
15     for(int i=1;i<=n;i++)
16         s[i]=i*i*i*i;
17     for(int i=1;i<=n;i++)
18         for(int j=s[i];j<=m;j++)
19             f[j]=min(f[j],f[j-s[i]]+1);
20     printf("%d\n",f[m]);
21 }

这道题……比较容易看出来是个完全背包问题~

只不过要我们求最小值

递推关系f[v]=max{f[v],f[v-w[i]+c[i]]}

这里我们让i=1 to 18 (18^4>100000)

w[i]=i*i*i*i;c[i]=1;这里我们可以省略掉c[i]数组了

我们只需要将f[i]初始化为inf并且f[0]=0;

还有一些微小的改动

具体参考代码：

#include<bits/stdc++.h>
int f[200001],w[200001],n=18,m; using namespace std; //全局变量部分 int main() { memset(f,0xf,sizeof(f)); f[0]=0;cin>>m; //初始化数据 for(int i=1;i<=n;i++) w[i]=i*i*i*i; for(int i=1;i<=n;i++) //完全背包 for(int v=w[i];v<=m;++v) if(f[v]>f[v-w[i]]+1) f[v]=f[v-w[i]]+1; cout<<f[m]; }