题解：swj社会摇基础第一课

2024-09-05 00:01:35

题目链接

思路：dp,f[i]表示构成i所需要的最小步数

//swj么么哒

#include<bits/stdc++.h>

using namespace std;

int n;

const int N = 1000000;

int f[N],mi[N];

int cnt=0;

int main() {

	cin>>n;

	int i=1;

	while(i*i<=n/i){

		mi[++cnt]=i*i*i;

		i++;

	}

	memset(f,0x3f,sizeof f);

	f[0]=0;

	for(int i=1;i<=cnt;i++) {

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

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

		}

	}

	cout<<f[n];

}

最新文章

热门文章