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

01背包和完全背包

article 2024/12/28 19:33:01

01背包

最大约数和

题目链接点击这里

题目描述

选取和不超过 $S$ 的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。

输入格式

输入一个正整数 $S$ 。

输出格式

输出最大的约数之和。

样例 #1

样例输入 #1

样例输出 #1

提示

【样例说明】

取数字 $4$ 和 $6$ ，可以得到最大值 $(1 + 2) + (1 + 2 + 3) = 9$ 。

【数据规模】

对于 $\%$ 的数据， $\le S \le 1000$ 。

源代码

#include <iostream>
using namespace std;
const int N = 5050;
int f[N],v[N],w[N];
int getsum(int x)
{
	int ans = 0;
	for(int i = 1;i < x;i ++ )
	{
		if(x % i == 0)ans += i;
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int s;
	cin >> s;
	for(int i = 1;i <= s;i ++ )
	{
		w[i] = getsum(i);
		v[i] = i;
	}
	for(int i = 2;i <= s;i ++ )
	{
		for(int j = s;j >= v[i];j -- )
		{
			f[j] = max(f[j],f[j - v[i]] + w[i]);
		}
	}
	cout << f[s];
	return 0;
}

[NOIP2005 普及组] 采药

题目链接点击这里

题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入格式

第一行有 $2$ 个整数 $T$ （ $\le T \le 1000$ ）和 $M$ （ $\le M \le 100$ ），用一个空格隔开， $T$ 代表总共能够用来采药的时间， $M$ 代表山洞里的草药的数目。

接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$ ）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出在规定的时间内可以采到的草药的最大总价值。

样例 #1

样例输入 #1

样例输出 #1

提示

【数据范围】

对于 $30\%$ 的数据， $\le 10$ ；
对于全部的数据， $\le 100$ 。

【题目来源】

NOIP 2005 普及组第三题

源代码

#include <iostream>
using namespace std;
const int N = 5050;
int f[N],v[N],w[N];
int n,m;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> m >> n;
	for(int i = 1;i <= n;i ++ )cin >> v[i] >> w[i];
	for(int i = 1;i <= n;i ++ )
	{
		for(int j = m;j >= v[i];j -- )
		{
			f[j] = max(f[j],f[j - v[i]] + w[i]);
		}
	}
	cout << f[m];
	return 0;
}

[HAOI2012] 音量调节

题目描述点击这里

题目描述

一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都需要改变一次音量。在演出开始之前，他已经做好一个列表，里面写着每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选择调高也可以调低。

音量用一个整数描述。输入文件中整数 $b e g in L e v e l$ ，代表吉他刚开始的音量，整数 $ma xL e v e l$ ，代表吉他的最大音量。音量不能小于 $0$ 也不能大于 $ma xL e v e l$ 。输入中还给定了 $n$ 个整数 $c_1,c_2,c_3,\cdots,c_n$ ，表示在第 $i$ 首歌开始之前吉他手想要改变的音量是多少。

吉他手想以最大的音量演奏最后一首歌，你的任务是找到这个最大音量是多少。

输入格式

第一行依次为三个整数 $n$ ， $b e g in L e v e l$ 和 $ma xL e v e l$ 。

第二行依次为 $n$ 个整数 $c_1,c_2,c_3,\cdots,c_n$ 。

输出格式

输出演奏最后一首歌的最大音量。如果吉他手无法避免音量低于 $0$ 或者高于 $ma xL e v e l$ ，输出 -1。

样例 #1

样例输入 #1

3 5 10
5 3 7

样例输出 #1

提示

$1\le n\le 50$ ， $1\le c_i\le maxLevel$ ， $1\le maxLevel\le 1000$ ， $0\le beginLevel\le maxLevel$ 。

源代码

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 5050;
ll f[N][N],v[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n,l,r;
	cin >> n >> l >> r;
	f[0][l] = 1;
	for(ll i = 1;i <= n;i ++ )cin >> v[i];
	for(ll i = 1;i <= n;i ++ )
	{
		for(ll j = r;j >= 0;j -- )
		{
			if(f[i - 1][j - v[i]] == 1 && j - v[i] >= 0)f[i][j] = 1;
			if(f[i - 1][j + v[i]] == 1 && j + v[i] <= r)f[i][j] = 1;
		}
	}
	int flag = 0;
	for(int i = r;i >= 1;i -- )
	{
		if(f[n][i] == 1)
		{
			flag = 1;
			cout << i << endl;
			break;
		}
	}
	if(flag == 0)cout << "-1" << endl;
	return 0;
}

[NOIP2001 普及组] 装箱问题

题目链接点击这里

题目描述

有一个箱子容量为 $V$ ，同时有 $n$ 个物品，每个物品有一个体积。

现在从 $n$ 个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。输出这个最小值。

输入格式

第一行共一个整数 $V$ ，表示箱子容量。

第二行共一个整数 $n$ ，表示物品总数。

接下来 $n$ 行，每行有一个正整数，表示第 $i$ 个物品的体积。

输出格式

共一行一个整数，表示箱子最小剩余空间。

样例 #1

样例输入 #1

样例输出 #1

提示

对于 $100\%$ 数据，满足 $\le 30$ ， $\le V \le 20000$ 。

【题目来源】

NOIP 2001 普及组第四题

源代码

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 10000000 + 10;
ll f[N],v[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n,m;
	cin >> m >> n;
	for(ll i = 1;i <= n;i ++ )cin >> v[i];
	for(ll i = 1;i <= n;i ++ )
	{
		for(ll j = m;j >= v[i];j -- )
		{
			f[j] = max(f[j],f[j - v[i]] + v[i]);
		}
	}
	cout << m - f[m] << endl;
	return 0;
}

[NOIP2006 普及组] 开心的金明

题目链接点击这里

题目描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 $N$ 元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 $N$ 元。于是，他把每件物品规定了一个重要度，分为 $5$ 等：用整数 $1 - 5$ 表示，第 $5$ 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过 $N$ 元（可以等于 $N$ 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第 $j$ 件物品的价格为 $v [j]$ ，重要度为 $w [j]$ ，共选中了 $k$ 件物品，编号依次为 $j_1,j_2,…,j_k$ ，则所求的总和为：

$v[j_1] \times w[j_1]+v[j_2] \times w[j_2]+ …+v[j_k] \times w[j_k]$ 。

请你帮助金明设计一个满足要求的购物单。

输入格式

第一行，为 $2$ 个正整数，用一个空格隔开： $n, m$ （其中 $N (< 30000)$ 表示总钱数， $m (< 25)$ 为希望购买物品的个数。）

从第 $2$ 行到第 $m + 1$ 行，第 $j$ 行给出了编号为 $j - 1$ 的物品的基本数据，每行有 $2$ 个非负整数$ v p $（其中$ v $表示该物品的价格$ (v \le 10000) $，$ p$表示该物品的重要度( $1 - 5$ )

输出格式

$1$ 个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值 $(< 100000000)$ 。

样例 #1

样例输入 #1

样例输出 #1

提示

NOIP 2006 普及组第二题

源代码

#include <iostream>
using namespace std;
const int N = 1000000 + 10;
int f[N],v[N],w[N];
int n,m;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> m >> n;
	for(int i = 1;i <= n;i ++ )
	{
		cin >> v[i] >> w[i];
		w[i] *= v[i];
	}
	for(int i = 1;i <= n;i ++ )
	{
		for(int j = m;j >= v[i];j -- )
		{
			f[j] = max(f[j],f[j - v[i]] + w[i]);
		}
	}
	cout << f[m];
	return 0;
}

小A点菜

题目链接点击这里

题目背景

uim 神犇拿到了 uoi 的 ra（镭牌）后，立刻拉着基友小 A 到了一家……餐馆，很低端的那种。

uim 指着墙上的价目表（太低级了没有菜单），说：“随便点”。

题目描述

不过 uim 由于买了一些书，口袋里只剩 $M$ 元 $\le 10000)$ 。

餐馆虽低端，但是菜品种类不少，有 $N$ 种 $\le 100)$ ，第 $i$ 种卖 $a_i$ 元 $(a_i \le 1000)$ 。由于是很低端的餐馆，所以每种菜只有一份。

小 A 奉行“不把钱吃光不罢休”，所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。

由于小 A 肚子太饿，所以最多只能等待 $1$ 秒。

输入格式

第一行是两个数字，表示 $N$ 和 $M$ 。

第二行起 $N$ 个正数 $a_i$ （可以有相同的数字，每个数字均在 $1000$ 以内）。

输出格式

一个正整数，表示点菜方案数，保证答案的范围在 int 之内。

样例 #1

样例输入 #1

4 4
1 1 2 2

样例输出 #1

提示

2020.8.29，增添一组 hack 数据 by @yummy

源代码

#include <iostream>
using namespace std;
const int N = 5000 + 10;
int f[N][N],v[N];
int n,m;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;i ++ )cin >> v[i];
	for(int i = 1;i <= n;i ++ )
	{
		for(int j = 1;j <= m;j ++ )
		{
			if(j == v[i])f[i][j] = f[i - 1][j] + 1;
			if(j < v[i])f[i][j] = f[i - 1][j];
			if(j > v[i])f[i][j] = f[i - 1][j] + f[i - 1][j - v[i]];
		}
	}
	cout << f[n][m];
	return 0;
}

[USACO07DEC]Charm Bracelet S

题目描述

Bessie has gone to the mall’s jewelry store and spies a charm bracelet. Of course, she’d like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weight Wi (1 ≤ Wi ≤ 400), a ‘desirability’ factor Di (1 ≤ Di ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880).

Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.

有 $N$ 件物品和一个容量为 $M$ 的背包。第 $i$ 件物品的重量是 $W_i$ ，价值是 $D_i$ 。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入格式

* Line 1: Two space-separated integers: N and M

* Lines 2…N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di

第一行：物品个数 $N$ 和背包大小 $M$ 。

第二行至第 $N + 1$ 行：第 $i$ 个物品的重量 $W_i$ 和价值 $D_i$ 。

输出格式

* Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints

输出一行最大价值。

样例 #1

样例输入 #1

样例输出 #1

源代码

#include <iostream>
#include <cmath>
using namespace std;
const int N = 5000 + 50;
int f[N],v[N],w[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin >> n >> m;
	for(int i = 1;i <= n;i ++ )cin >> v[i] >> w[i];
	for(int i = 1;i <= n;i ++ )
	{
		for(int j = m;j >= v[i];j -- )
		{
			f[j] = max(f[j],f[j - v[i]] + w[i]);
		}
	}
	cout << f[m] << endl;
	return 0;
}

[蓝桥杯 2021 省 AB] 砝码称重

题目链接点击这里

题目描述

你有一架天平和 $N$ 个砝码, 这 $N$ 个砝码重量依次是 $W_{1}, W_{2}, \cdots, W_{N}$ 。请你计算一共可以称出多少种不同的重量?

注意砝码可以放在天平两边。

输入格式

输入的第一行包含一个整数 $N$ 。

第二行包含 $N$ 个整数: $W_{1}, W_{2}, W_{3}, \cdots, W_{N}$ 。

输出格式

输出一个整数代表答案。

样例 #1

样例输入 #1

3
1 4 6

样例输出 #1

提示

【样例说明】

能称出的 10 种重量是: $1 、 2 、 3 、 4 、 5 、 6 、 7 、 9 、 10 、 11$ 。

$\begin{aligned} &1=1 \\ &2=6-4(\text { 天平一边放 } 6, \text { 另一边放 4) } \\ &3=4-1 \\ &4=4 \\ &5=6-1 \\ &6=6 \\ &7=1+6 \\ &9=4+6-1 \\ &10=4+6 \\ &11=1+4+6 \end{aligned}$

【评测用例规模与约定】

对于 $\%$ 的评测用例, $\leq N \leq 15$ 。

对于所有评测用例, $\leq N \leq 100, N$ 个砝码总重不超过 $10^5$ 。

蓝桥杯 2021 第一轮省赛 A 组 F 题（B 组 G 题）。

源代码

#include <iostream>
#include <stdlib.h>
using namespace std;
typedef long long ll;
const int N = 5050;
ll f[110][100010], v[N];
int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n, sum = 0, ans = 0;
	cin >> n;
	for (ll i = 1; i <= n; i ++ ) 
	{
		cin >> v[i];
		sum += v[i];
	}
	for (ll i = 1; i <= n; i ++ ) 
	{
		for (ll j = sum;j > 0;j -- ) 
		{
			f[i][j] = f[i - 1][j];
			if(!f[i][j])
			{
				if(j == v[i])f[i][j] = 1;
				if(f[i - 1][j + v[i]])f[i][j] = 1;
				if(f[i - 1][abs(j - v[i])])f[i][j] = 1;
			}
		}
	}
	for (int i = 1; i <= sum; i ++ ) 
	{
		if (f[n][i] == 1)ans ++ ;
	}
	cout << ans << endl;
	return 0;
}

L国的战斗之间谍

题目链接点击此处

题目背景

L国即将与I国发动战争！！

题目描述

俗话说的好：“知己知彼，百战不殆”。L国的指挥官想派出间谍前往I国，于是，选人工作就落到了你身上。

你现在有N个人选，每个人都有这样一些数据：A（能得到多少资料）、B（伪装能力有多差）、C（要多少工资）。已知敌人的探查间谍能力为M（即去的所有人B的和要小于等于M）和手头有X元钱，请问能拿到多少资料？

输入格式

N M X

A1 B1 C1

A2 B2 C2

………………

AN BN CN

输出格式

能得到的资料总数

样例 #1

样例输入 #1

样例输出 #1

提示

数据范围：

1≤n≤100,1≤m≤1000, 1≤x≤1000

源代码

#include <iostream>
#include <stdlib.h>
using namespace std;
typedef long long ll;
const int N = 5050;
ll f[N][N],a[N],b[N],c[N];
int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n,M,X;
	cin >> n >> M >> X;
	for(int i = 1;i <= n;i ++ )cin >> a[i] >> b[i] >> c[i];
	for(int i = 1;i <= n;i ++ )
	{
		for(int j = M;j >= b[i];j -- )
		{
			for(int k = X;k >= c[i];k -- )
			{
				f[j][k] = max(f[j][k],f[j - b[i]][k - c[i]] + a[i]);
			}
		}
	}
	cout << f[M][X] << endl;
	return 0;
}

小书童——刷题大军

题目链接点击这里

题目背景

数学是火，点亮物理的灯；物理是灯，照亮化学的路；化学是路，通向生物的坑；生物是坑，埋葬学理的人。文言是火，点亮历史宫灯；历史是灯，照亮社会之路；社会是路，通向哲学大坑；哲学是坑，埋葬文科生。——小A

题目描述

小A“刷题”十分猖狂，明目张胆地“刷题”。他现在在小书童里发现了n样他喜欢的“题目”，每“题”都有他的需要时间，而老师布置了m项作业，每项作业都有它的需要时间及分值，老师规定k分以上算及格。小A只剩r个单位时间，他想在及格的基础上更多地“刷题”。

输入格式

第一行：n m k r。第二行：n个数，代表每“题”他的需要时间。第三行：m个数。表示每项作业它的需要时间。第四行：m个数。代表每项作业它的分值。

输出格式

一个数，代表小A能刷几道题

样例 #1

样例输入 #1

3 4 20 100
15 20 50
10 15 40 40
5 5 10 15

样例输出 #1

提示

没有不能及格的情况

对于100%的数据， $n\le 10,m\le 10,k\le 50,r\le 150$

源代码

#include <iostream>
using namespace std;
typedef long long ll;
const int N = 5050;
ll f1[N],f2[N],pt[N],ht[N],w[N];
int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n,m,k,r;
	cin >> n >> m >> k >> r;
	for(int i = 1;i <= n;i ++ )cin >> pt[i];
	for(int i = 1;i <= m;i ++ )cin >> ht[i];
	for(int i = 1;i <= m;i ++ )cin >> w[i];
	for(int i = 1;i <= k;i ++ )f1[i] = 5201314;
	for(int i = 1;i <= m;i ++ )
	{
		for(int j = k;j >= w[i];j -- )
		{
			f1[j] = min(f1[j],f1[j - w[i]] + ht[i]);
		}
	}
	r -= f1[k];
	for(int i = 1;i <= n;i ++ )
	{
		for(int j = r;j >= pt[i];j -- )
		{
			f2[j] = max(f2[j],f2[j - pt[i]] + 1);
		}
	}
	cout << f2[r] << endl;
	return 0;
}

[USACO09OCT]Bessie’s Weight Problem G

题目链接点击这里

题目描述

Bessie 像她的诸多姊妹一样，因为从 Farmer John 的草地吃了太多美味的草而长出了太多的赘肉。所以 FJ 将她置于一个及其严格的节食计划之中。她每天不能吃多过 $\le H \le 45,000)$ 公斤的干草。 Bessie 只能吃一整捆干草；当她开始吃一捆干草的之后就再也停不下来了。她有一个完整的 $\le N \le 500)$ 捆可以给她当作晚餐的干草的清单。她自然想要尽量吃到更多的干草。很自然地，每捆干草只能被吃一次（即使在列表中相同的重量可能出现2次，但是这表示的是两捆干草，其中每捆干草最多只能被吃掉一次）。给定一个列表表示每捆干草的重量 $S_i (1 \le S_i \le H)$ , 求 Bessie 不超过节食的限制的前提下可以吃掉多少干草（注意一旦她开始吃一捆干草就会把那一捆干草全部吃完）。

输入格式

第一行有两个由空格隔开的整数 $H$ 和 $N$ 。

第 $2$ 到第 $N + 1$ 行，第 $i + 1$ 行是一个单独的整数，表示第 $i$ 捆干草的重量 $S_i$ 。

输出格式

第一行一个单独的整数表示 Bessie 在限制范围内最多可以吃多少公斤的干草。

样例 #1

样例输入 #1

样例输出 #1

提示

输入说明

有四捆草，重量分别是 $15, 19, 20$ 和 $21$ 。Bessie 在 $56$ 公斤的限制范围内想要吃多少就可以吃多少。

输出说明

Bessie 可以吃 $3$ 捆干草（重量分别为 $15, 20, 21$ ）。恰好达到她的 $56$ 公斤的限制。

源代码

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 10000000 + 10;
ll f[N],v[N];
int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n,m;
	cin >> m >> n;
	for(int i = 1;i <= n;i ++ )cin >> v[i];
	for(int i = 1;i <= n;i ++ )
	{
		for(int j = m;j >= v[i];j -- )
		{
			f[j] = max(f[j],f[j - v[i]] + v[i]);
		}
	}
	cout << f[m] << endl;
	return 0;
}

精卫填海

题目描述

题目链接点击这里
【版权说明】

本题为改编题。

【问题描述】

发鸠之山，其上多柘木。有鸟焉，其状如乌，文首，白喙，赤足，名曰精卫，其名自詨。是炎帝之少女，名曰女娃。女娃游于东海，溺而不返，故为精卫。常衔西山之木石，以堙于东海。——《山海经》

精卫终于快把东海填平了！只剩下了最后的一小片区域了。同时，西山上的木石也已经不多了。精卫能把东海填平吗？

事实上，东海未填平的区域还需要至少体积为v的木石才可以填平，而西山上的木石还剩下n块，每块的体积和把它衔到东海需要的体力分别为k和m。精卫已经填海填了这么长时间了，她也很累了，她还剩下的体力为c。

输入格式

输入文件的第一行是三个整数：v、n、c。

从第二行到第n+1行分别为每块木石的体积和把它衔到东海需要的体力。

输出格式

输出文件只有一行，如果精卫能把东海填平，则输出她把东海填平后剩下的最大的体力，否则输出’Impossible’（不带引号）。

样例 #1

样例输入 #1

100 2 10
50 5
50 5

样例输出 #1

样例 #2

样例输入 #2

10 2 1
50 5
10 2

样例输出 #2

Impossible

提示

【数据范围】

对于20%的数据，0<n<=50。

对于50%的数据，0<n<=1000。

对于100%的数据，0<n<=10000，所有读入的数均属于[0,10000]，最后结果<=c。

源代码

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 10000000 + 10;
ll f[N],v[N],w[N];
int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll V,N,C;
	cin >> V >> N >> C;
	for(int i = 1;i <= N;i ++ )cin >> v[i] >> w[i];
	for(int i = 1;i <= N;i ++ )
	{
		for(int j = C;j >= w[i];j -- )
		{
			f[j] = max(f[j],f[j - w[i]] + v[i]);
		}
	}
	if(f[C] < V)cout << "Impossible" << endl;
	else
	{
		for(int i = 0;i <= C;i ++ )
		{
			if(f[i] >= V)
			{
				cout << C - i << endl;
				break;
			}
		}
	}
	return 0;
}

[RC-04] 01 背包

题目链接点击这里

题目描述

有一个容积为 $+\infty $ 的背包，你要往里面放物品。

你有 $n$ 个物品，第 $i$ 个体积为 $a_i$ 。

你有一个幸运数字 $p$ ，若放入的物品体积和为 $k$ ，你会得到 $p^k$ 的收益。特别地， $0^0=1$ 。

求所有 $2^n$ 种放入物品的方案的收益和。答案很大，因此请输出它对 $998244353$ 取模的值。

输入格式

第一行两个整数 $n, p$ 。

接下来一行 $n$ 个正整数 $a_1\sim a_n$ ，描述这 $n$ 个物品的体积。

输出格式

输出一个整数，为所有 $2^n$ 种方案的收益和对 $998244353$ 取模的值。

样例 #1

样例输入 #1

2 2
1 4

样例输出 #1

提示

【样例解释】

答案为 $2^0+2^1+2^4+2^5=51$ 。

【数据范围】

对于所有数据， $1\le n\le 10^6$ ， $0\le p,a_i<998244353$ 。

详细数据范围如下表：

测试点编号	$n$	$p$	$\sum_{i=1}^na_i$	每测试点分数
$1$		$= 0$		$2$
$2\sim 5$	$\le 22$			$6$
$6\sim 9$	$\le 1000$		$\le 1000$	$6$
$10\sim 14$	$\le 100000$		$\le 100000$	$5$
$15$				$25$

源代码

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 1000000 + 10;
const ll mod = 998244353;
ll f[N],v[N];
ll fun(ll a,ll b,ll p)
{
    if(b == 0)return 1 % p;
    a %= p;
    ll ans = 1;
    while(b > 0)
    {
        if(b & 1)
        {
            ans *= a;
            ans %= p;
        }
        b >>= 1;
        a = (a * a) % p;
    }
    return ans;
}
int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n,a,ans = 1;
	cin >> n >> a;
	for(int i = 1;i <= n;i ++ )cin >> v[i];
	for(int i = 1;i <= n;i ++ )
	{
		ans *= (fun(a,v[i],mod) + 1);
		ans %= mod;
	}
	cout << ans << endl;
	return 0;
}

榨取kkksc03

题目描述

洛谷 2 的团队功能是其他任何 OJ 和工具难以达到的。借助洛谷强大的服务器资源，任何学校都可以在洛谷上零成本的搭建 OJ 并高效率的完成训练计划。

为什么说是搭建 OJ 呢？为什么高效呢？

因为，你可以上传私有题目，团队外别人是无法看到的。我们还能帮你们评测！

你可以创建作业，给组员布置任务，查看组员的完成情况，还可以点评任意一份代码！

你可以创建比赛！既可以是 OI 赛制还可以是 ICPC 赛制！既可以是团队内部的私有比赛，也可以公开赛，甚至可以指定谁可以参加比赛。这样，搞“x 校联赛”最合适不过了。洛谷凭借这个功能，希望能够提供公开及私有比赛的另外一个平台。

值得说明的是，本次比赛就是采用团队私有题目+邀请比赛的机制。

洛谷的运营组决定，如果一名 OIer 向他的教练推荐洛谷，并能够成功的使用（成功使用的定义是：该团队有 $20$ 个或以上的成员，上传 $10$ 道以上的私有题目，布置过一次作业并成功举办过一次公开比赛），那么他可以浪费掉 kkksc03 的一些时间的同时消耗掉 kkksc03 的一些金钱以满足自己的一个愿望。

kkksc03 的时间和金钱是有限的，所以他很难满足所有同学的愿望。所以他想知道在自己的能力范围内，最多可以完成多少同学的愿望？

输入格式

第一行三个整数 $n, M, T$ ，表示一共有 $n$ （ $\le n \le 100$ ）个愿望， kkksc03 的手上还剩 $M$ （ $\le M \le 200$ ）元，他的暑假有 $T$ （ $\le T \le 200$ ）分钟时间。

第 $2$ ~ $n + 1$ 行 $m_{i}$ , $t_{i}$ 表示第 $i$ 个愿望所需要的金钱和时间。

输出格式

一行，一个数，表示 kkksc03 最多可以实现愿望的个数。

样例 #1

样例输入 #1

样例输出 #1

源代码

未优化

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 200 + 10;
ll f[N][N][N],m[110],t[110];
int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n,M,T;
	cin >> n >> M >> T;
	for(int i = 1;i <= n;i ++ )cin >> m[i] >> t[i];
	for(int i = 1;i <= n;i ++ )
	{
		for(int j = 0;j <= M;j ++ )
		{
			for(int k = 0;k <= T;k ++ )
			{
				if(j >= m[i] && k >= t[i])f[i][j][k] = max(f[i - 1][j][k],f[i - 1][j - m[i]][k - t[i]] + 1);
				else f[i][j][k] = f[i - 1][j][k];
			}
		}
	}
	cout << f[n][M][T] << endl;
	return 0;
}

优化

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 200 + 10;
ll f[N][N],m[110],t[110];
int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n,M,T;
	cin >> n >> M >> T;
	for(int i = 1;i <= n;i ++ )cin >> m[i] >> t[i];
	for(int i = 1;i <= n;i ++ )
	{
		for(int j = M;j >= m[i];j -- )
		{
			for(int k = T;k >= t[i];k -- )
			{
				f[j][k] = max(f[j][k],f[j - m[i]][k - t[i]] + 1);
			}
		}
	}
	cout << f[M][T] << endl;
	return 0;
}

kkksc03考前临时抱佛脚

题目链接点击这里

题目背景

kkksc03 的大学生活非常的颓废，平时根本不学习。但是，临近期末考试，他必须要开始抱佛脚，以求不挂科。

题目描述

这次期末考试，kkksc03 需要考 $4$ 科。因此要开始刷习题集，每科都有一个习题集，分别有 $s_1,s_2,s_3,s_4$ 道题目，完成每道题目需要一些时间，可能不等（ $A_1,A_2,\ldots,A_{s_1}$ ， $B_1,B_2,\ldots,B_{s_2}$ ， $C_1,C_2,\ldots,C_{s_3}$ ， $D_1,D_2,\ldots,D_{s_4}$ ）。

kkksc03 有一个能力，他的左右两个大脑可以同时计算 $2$ 道不同的题目，但是仅限于同一科。因此，kkksc03 必须一科一科的复习。

由于 kkksc03 还急着去处理洛谷的 bug，因此他希望尽快把事情做完，所以他希望知道能够完成复习的最短时间。

输入格式

本题包含 $5$ 行数据：第 $1$ 行，为四个正整数 $s_1,s_2,s_3,s_4$ 。

第 $2$ 行，为 $A_1,A_2,\ldots,A_{s_1}$ 共 $s_1$ 个数，表示第一科习题集每道题目所消耗的时间。

第 $3$ 行，为 $B_1,B_2,\ldots,B_{s_2}$ 共 $s_2$ 个数。

第 $4$ 行，为 $C_1,C_2,\ldots,C_{s_3}$ 共 $s_3$ 个数。

第 $5$ 行，为 $D_1,D_2,\ldots,D_{s_4}$ 共 $s_4$ 个数，意思均同上。

输出格式

输出一行,为复习完毕最短时间。

样例 #1

样例输入 #1

样例输出 #1

提示

$1\leq s_1,s_2,s_3,s_4\leq 20$ 。

$1\leq A_1,A_2,\ldots,A_{s_1},B_1,B_2,\ldots,B_{s_2},C_1,C_2,\ldots,C_{s_3},D_1,D_2,\ldots,D_{s_4}\leq60$ 。

源代码

未优化

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 1000 + 10;
int f[N][N],v[N],ans = 0;
void solve(int n)
{
	memset(f,0,sizeof(f));
	memset(v,0,sizeof(v));
	int sum = 0;
	for(int i = 1;i <= n;i ++ )
	{
		cin >> v[i];
		sum += v[i];
	}
	for(int i = 1;i <= n;i ++ )
	{
		for(int j = 0;j <= sum / 2;j ++ )
		{
			if(j >= v[i])f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i]] + v[i]);
			else f[i][j] = f[i - 1][j];
		}
	}
	ans += sum - f[n][sum / 2];
}
int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll s1,s2,s3,s4;
	cin >> s1 >> s2 >> s3 >> s4;
	solve(s1);
	solve(s2);
	solve(s3);
	solve(s4);
	cout << ans << endl;
	return 0;
}

优化

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 1000 + 10;
int f[N],v[N],ans = 0;
void solve(int n)
{
	memset(f,0,sizeof(f));
	memset(v,0,sizeof(v));
	int sum = 0;
	for(int i = 1;i <= n;i ++ )
	{
		cin >> v[i];
		sum += v[i];
	}
	for(int i = 1;i <= n;i ++ )
	{
		for(int j = sum / 2;j >= v[i];j -- )
		{
			f[j] = max(f[j],f[j - v[i]] + v[i]);
		}
	}
	ans += sum - f[sum / 2];
}
int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll s1,s2,s3,s4;
	cin >> s1 >> s2 >> s3 >> s4;
	solve(s1);
	solve(s2);
	solve(s3);
	solve(s4);
	cout << ans << endl;
	return 0;
}

完全背包

[USACO3.1]总分 Score Inflation

题目链接点击这里

题目背景

选手在我们 USACO 的竞赛中的得分越多我们越高兴。

我们试着设计我们的竞赛以便人们能尽可能的多得分,这需要你的帮助。

题目描述

我们可以从几个种类中选取竞赛的题目,这里的一个"种类"是指一个竞赛题目的集合,解决集合中的题目需要相同多的时间并且能得到相同的分数。

你的任务是写一个程序来告诉 USACO 的职员,应该从每一个种类中选取多少题目，使得解决题目的总耗时在竞赛规定的时间里并且总分最大。

输入格式

输入的第一行是用空格隔开的两个整数，分别代表竞赛时间 $m$ 和题目类 $n$ 。

第 $2$ 到第 $(n + 1)$ 行，每行两个用空格隔开的整数，第 $(i + 1)$ 行的整数 $p_i, t_i$ 分别代表解决第 $i$ 类题得到的分数和需要花费的时间。

既然是某一类题目，那么这一类题目可以重复选择。

输出格式

输出一行一个整数，代表最大的总分。

样例 #1

样例输入 #1

样例输出 #1

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $\leq n \leq 10^4$ ， $\leq p_i, t_i \leq 10^4$ 。

源代码

#include <iostream>
using namespace std;
const int N = 1000000 + 10;
int f[N],v[N],w[N];
int n,m;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> m >> n;
	for(int i = 1;i <= n;i ++ )cin >> w[i] >> v[i];
	for(int i = 1;i <= n;i ++ )
	{
		for(int j = v[i];j <= m;j ++ )
		{
			f[j] = max(f[j],f[j - v[i]] + w[i]);
		}
	}
	cout << f[m];
	return 0;
}

A+B Problem（再升级）

题目链接点击这里

题目背景

题目名称是吸引你点进来的。

实际上该题还是很水的。

题目描述

$1 + 1 = ?$ 显然是 $2$ 。
$a + b = ?$ P1001 回看不谢。
哥德巴赫猜想似乎已呈泛滥趋势。

以上纯属个人吐槽

给定一个正整数 $n$ ，求将其分解成若干个素数之和的方案总数。

输入格式

一行一个正整数 $n$ 。

输出格式

一行一个整数表示方案总数。

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

样例解释

存在如下三种方案：

$7 = 7$ 。
$7 = 2 + 5$ 。
$7 = 2 + 2 + 3$ 。

数据范围及约定

对于 $30\%$ 的数据 $1\le n\le 10$ 。
对于 $100\%$ 的数据， $1\le n\le 10^3$ 。

源代码

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 5050;
ll f[N],v[N];
ll cnt = 0;
bool prime(ll n)
{
	for(ll i = 2;i <= sqrt(n);i ++ )
	{
		if(n % i == 0)return false;
	}
	return true;
}
void Init(ll n)
{
	for(ll i = 2;i <= n;i ++ )
	{
		if(prime(i))
		{
			cnt ++ ;
			v[cnt] = i;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n;
	cin >> n;
	Init(n);
	f[0] = 1;
	for(ll i = 1;i <= cnt;i ++ )
	{
		for(ll j = v[i];j <= n;j ++ )
		{
			f[j] += f[j - v[i]];
		}
	}
	cout << f[n];
	return 0;
}

疯狂的采药

题目链接点击此处

题目背景

此题为纪念 LiYuxiang 而生。

题目描述

LiYuxiang 是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是 LiYuxiang，你能完成这个任务吗？

此题和原题的不同点：

$1$ . 每种草药可以无限制地疯狂采摘。

$2$ . 药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！

输入格式

输入第一行有两个整数，分别代表总共能够用来采药的时间 $t$ 和代表山洞里的草药的数目 $m$ 。

第 $2$ 到第 $(m + 1)$ 行，每行两个整数，第 $(i + 1)$ 行的整数 $a_i, b_i$ 分别表示采摘第 $i$ 种草药的时间和该草药的价值。

输出格式

输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

样例 #1

样例输入 #1

样例输出 #1

提示

数据规模与约定

对于 $30\%$ 的数据，保证 $\le 10^3$ 。
对于 $100\%$ 的数据，保证 $\leq m \le 10^4$ ， $\leq t \leq 10^7$ ，且 $\leq m \times t \leq 10^7$ ， $\leq a_i, b_i \leq 10^4$ 。

源代码

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 10000000 + 10;
ll f[N],v[N],w[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n,m;
	cin >> m >> n;
	for(ll i = 1;i <= n;i ++ )cin >> v[i] >> w[i];
	for(ll i = 1;i <= n;i ++ )
	{
		for(ll j = v[i];j <= m;j ++ )
		{
			f[j] = max(f[j],f[j - v[i]] + w[i]);
		}
	}
	cout << f[m] << endl;
	return 0;
}

NASA的食物计划

题目链接点击这里

题目背景

NASA（美国航空航天局）因为航天飞机的隔热瓦等其他安全技术问题一直大伤脑筋，因此在各方压力下终止了航天飞机的历史，但是此类事情会不会在以后发生，谁也无法保证。所以，在遇到这类航天问题时，也许只能让航天员出仓维修。但是过多的维修会消耗航天员大量的能量，因此 NASA 便想设计一种食品方案，使体积和承重有限的条件下多装载一些高卡路里的食物。

题目描述

航天飞机的体积有限，当然如果载过重的物品，燃料会浪费很多钱，每件食品都有各自的体积、质量以及所含卡路里。在告诉你体积和质量的最大值的情况下，请输出能达到的食品方案所含卡路里的最大值，当然每个食品只能使用一次。

输入格式

第一行 $2$ 个整数，分别代表体积最大值 $h$ 和质量最大值 $t$ 。

第二行 $1$ 个整数代表食品总数 $n$ 。

接下来 $n$ 行每行 $3$ 个数体积 $h_i$ ，质量 $t_i$ ，所含卡路里 $k_i$ 。

输出格式

一个数，表示所能达到的最大卡路里（int 范围内）

样例 #1

样例输入 #1

样例输出 #1

提示

对于 $100\%$ 的数据， $h,t,h_i,t_i \le 400$ ， $\le 50$ ， $k_i \le 500$ 。

源代码

未优化

#include <iostream>
#include <cmath>
using namespace std;
const int N = 500 + 50;
int f[N][N][N],v[N],w[N],kal[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int m1,m2;
	cin >> m1 >> m2;
	int n;
	cin >> n;
	for(int i = 1;i <= n;i ++ )cin >> v[i] >> w[i] >> kal[i];
	for(int i = 1;i <= n;i ++ )
	{
		for(int j = m1;j >= 0;j -- )
		{
			for(int k = m2;k >= 0;k -- )
			{
				if(j >= v[i] && k >= w[i])f[i][j][k] = max(f[i - 1][j][k],f[i - 1][j - v[i]][k - w[i]] + kal[i]);
				else f[i][j][k] = f[i - 1][j][k];
			}
		}
	}
	cout << f[n][m1][m2] << endl;
	return 0;
}

优化版

#include <iostream>
#include <cmath>
using namespace std;
const int N = 5000 + 50;
int f[N][N],v[N],w[N],kal[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int m1,m2;
	cin >> m1 >> m2;
	int n;
	cin >> n;
	for(int i = 1;i <= n;i ++ )cin >> v[i] >> w[i] >> kal[i];
	for(int i = 1;i <= n;i ++ )
	{
		for(int j = m1;j >= v[i];j -- )
		{
			for(int k = m2;k >= w[i];k -- )
			{
				f[j][k] = max(f[j][k],f[j - v[i]][k - w[i]] + kal[i]);
			}
		}
	}
	cout << f[m1][m2] << endl;
	return 0;
}

[USACO08DEC]Hay For Sale S

题目链接点击这里

题面翻译

题目描述
农民john面临一个很可怕的事实，因为防范失措他存储的所有稻草给澳大利亚蟑螂吃光了，他将面临没有稻草喂养奶牛的局面。在奶牛断粮之前，john拉着他的马车到农民Don的农场中买一些稻草给奶牛过冬。已知john的马车可以装的下C(1 <= C <=50,000)立方的稻草。
农民Don有H(1 <= H <= 5,000)捆体积不同的稻草可供购买，每一捆稻草有它自己的体积(1 <= V_i <= C)。面对这些稻草john认真的计算如何充分利用马车的空间购买尽量多的稻草给他的奶牛过冬。
现在给定马车的最大容积C和每一捆稻草的体积Vi，john如何在不超过马车最大容积的情况下买到最大体积的稻草？他不可以把一捆稻草分开来买。

输入输出格式
输入格式：
第一行两个整数，分别为C和H
第2..H+1行:每一行一个整数代表第i捆稻草的体积Vi

输出格式：

一个整数，为john能买到的稻草的体积。
输入输出样例
输入样例#1：
7 3
2
6
5
输出样例#1：
7

翻译提供者：黑客集团_鬼

题目描述

Farmer John suffered a terrible loss when giant Australian cockroaches ate the entirety of his hay inventory, leaving him with nothing to feed the cows. He hitched up his wagon with capacity C (1 <= C <= 50,000) cubic units and sauntered over to Farmer Don’s to get some hay before the cows miss a meal.

Farmer Don had a wide variety of H (1 <= H <= 5,000) hay bales for sale, each with its own volume (1 <= V_i <= C). Bales of hay, you know, are somewhat flexible and can be jammed into the oddest of spaces in a wagon.

FJ carefully evaluates the volumes so that he can figure out the largest amount of hay he can purchase for his cows.

Given the volume constraint and a list of bales to buy, what is the greatest volume of hay FJ can purchase? He can’t purchase partial bales, of course. Each input line (after the first) lists a single bale FJ can buy.

约翰遭受了重大的损失：蟑螂吃掉了他所有的干草，留下一群饥饿的牛．他乘着容量为C(1≤C≤50000)个单位的马车，去顿因家买一些干草．顿因有H(1≤H≤5000)包干草，每一包都有它的体积Vi(l≤Vi≤C).约翰只能整包购买，

他最多可以运回多少体积的干草呢？

输入格式

* Line 1: Two space-separated integers: C and H

* Lines 2…H+1: Each line describes the volume of a single bale: V_i

输出格式

* Line 1: A single integer which is the greatest volume of hay FJ can purchase given the list of bales for sale and constraints.

样例 #1

样例输入 #1

样例输出 #1

提示

The wagon holds 7 volumetric units; three bales are offered for sale with volumes of 2, 6, and 5 units, respectively.

Buying the two smaller bales fills the wagon.

源代码

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 10000000 + 10;
ll f[N],v[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n,m;
	cin >> m >> n;
	for(ll i = 1;i <= n;i ++ )cin >> v[i];
	for(ll i = 1;i <= n;i ++ )
	{
		for(ll j = m;j >= v[i];j -- )
		{
			f[j] = max(f[j],f[j - v[i]] + v[i]);
		}
	}
	cout << f[m] << endl;
	return 0;
}

[AHOI2001]质数和分解

题目描述点击这里

题目描述

任何大于 $1$ 的自然数 $n$ 都可以写成若干个大于等于 $2$ 且小于等于 $n$ 的质数之和表达式(包括只有一个数构成的和表达式的情况)，并且可能有不止一种质数和的形式。例如， $9$ 的质数和表达式就有四种本质不同的形式：

$9 = 2 + 5 + 2 = 2 + 3 + 2 + 2 = 3 + 3 + 3 = 2 + 7$ 。

这里所谓两个本质相同的表达式是指可以通过交换其中一个表达式中参加和运算的各个数的位置而直接得到另一个表达式。

试编程求解自然数 $n$ 可以写成多少种本质不同的质数和表达式。

输入格式

文件中的每一行存放一个自然数 $\leq n \leq 200)$ 。

输出格式

依次输出每一个自然数 $n$ 的本质不同的质数和表达式的数目。

样例 #1

样例输入 #1

2
200

样例输出 #1

1
9845164

源代码

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 5050;
ll f[N];
bool prime(int n)
{
	for(int i = 2;i <= sqrt(n);i ++ )
	{
		if(n % i == 0)return false;	
	}
	return true;
}
int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n;
	while(cin >> n)
	{
		memset(f,0,sizeof(f));
		int idx = 0;
		int a[250];
		for(int i = 2;i <= n;i ++ )
		{
			if(prime(i))
			{
				idx ++ ;
				a[idx] = i;
			}
		}
		f[0] = 1;
		for(int i = 1;i <= idx;i ++ )
		{
			for(int j = a[i];j <= n;j ++ )
			{
				f[j] += f[j - a[i]];
			}
		}
		cout << f[n] << endl;
	}	
	return 0;
}

神奇的四次方数

题目链接点击这里

题目描述

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

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

输入格式

一行，一个整数m。

输出格式

一行，一个整数n。

样例 #1

样例输入 #1

样例输出 #1

提示

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

源代码

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 100000 + 10;
ll f[N],v[N];
int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n,m;
	cin >> m;
	n = ceil(sqrt(sqrt(m))+1);//向上取整 
	for(int i = 1;i <= n;i ++ )v[i] = i * i * i * i;
	f[0] = 0;
	for(int i = 1;i <= m;i ++ )f[i] = 5201314;
	for(int i = 1;i <= n;i ++ )
	{
		for(int j = v[i];j <= m;j ++ )
		{
			f[j] = min(f[j],f[j - v[i]] + 1);
		}
	}
	cout << f[m] << endl;
	return 0;
}