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


相关文章
|
10月前
|
【动态规划专栏】背包问题:1049. 最后一块石头的重量 II
【动态规划专栏】背包问题:1049. 最后一块石头的重量 II
77 0
|
10月前
完全背包问题
完全背包问题
66 0
完全背包与多重背包
完全背包与多重背包
258 0
洛谷P1616-疯狂的采药(完全背包)
洛谷P1616-疯狂的采药(完全背包)
AI助理

你好,我是AI助理

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