洛谷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


AC Code:


#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define min(x,y) (x<y ? x:y)
#define N 100001
int dp[N],a[N];
int m,ans;
int main() {
  scanf("%d",&m);
  for(int i=1;i<=18;i++) {//18^4=104976,本题中m最大为100000 
    a[i]=i*i*i*i;
  }
  memset(dp,0x3f3f3f,sizeof(dp));//要求最小,所以dp数组初始赋值为最大 
  dp[0]=0; 
  for(int i=1;i<=18;i++) {
    for(int j=a[i];j<=m;j++) {//每个数可以多次被选用,即完全背包
      //减去这个数的4次方,同时个数+1 
      dp[j]=min(dp[j],dp[j-a[i]]+1); 
    }
  }
  printf("%d\n",dp[m]);
  return 0;
}


目录
打赏
0
0
0
0
85
分享
相关文章
【洛谷 P2240】【深基12.例1】部分背包问题 题解(贪心算法)
**深基12.例1**是部分背包问题,$N$堆金币,每堆$(m_i, v_i)$,$T$承重限制。按金币单价降序装包,保证价值最大化。输入$N,T$及每堆金币详情,输出两位小数的最大价值。示例:输入$4,50$,输出$240.00$。AC代码使用C++,通过排序和迭代实现。
94 0
|
8月前
【洛谷】P2004 领地选择
洛谷 P2004 领地选择
76 2
【洛谷】P2004 领地选择
蓝桥杯:最大公约数 2020省赛 例题:既约分数
蓝桥杯:最大公约数 2020省赛 例题:既约分数
99 0
|
8月前
【洛谷】P1163 银行贷款
洛谷P1163 银行贷款
69 0
【洛谷】P1163 银行贷款
|
10月前
完全背包问题
完全背包问题
66 0
洛谷1102 A-B 暴力法
判断第 i 个数和 i 之后的每一个数的绝对值是否等于目标结果
洛谷P1616-疯狂的采药(完全背包)
洛谷P1616-疯狂的采药(完全背包)
洛谷 P1469 找筷子
题目描述 经过一段时间的紧张筹备,电脑小组的“RP餐厅”终于开业了,这天,经理LXC接到了一个定餐大单,可把大家乐坏了!员工们齐心协力按要求准备好了套餐正准备派送时,突然碰到一个棘手的问题,筷子!CX小朋友找出了餐厅中所有的筷子,但遗憾的是这些筷子长短不一,而我们都知道筷子需要长度一样的才能组成一双,更麻烦的是CX找出来的这些筷子数量为奇数,但是巧合的是,这些筷子中只有一只筷子是落单的,其余都成双,善良的你,可以帮CX找出这只落单的筷子的长度吗? 输入输出格式 输入格式:   第一行读入一个数N,它代表CX找到的筷子的根数。
1252 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等