零、前言

本蒟蒻真的不理解为什么用dp，明明是一个简单的贪心。

注：本题解仅代表本蒟蒻的个人意见，并无冒犯楼上楼下各位大佬的意思

一、输入

略

二、分析

1. 贪心策略

通过观察可以发现，我们要尽量多用 $2$ 号包装，因为可以装下 $5$ 颗糖。

但是，如果像样例2，只能用 $1$ 号包装呢？

其实很简单，只能用 $1$ 号包装，就是用0个 $2$ 号包装。

所以我们需要从 $\displaystyle \lfloor \frac{n}{5} \rfloor$ 循环到 $0$ 来确定最多的 $2$ 号包装数量。

2. 代码

for (int i = n / 5; i >= 0; i --)
    if ((n - i * 5) % 3 == 0) //判断包装方式是否合法
    {
        cout << i + (n - i * 5) / 3;
        return 0;
    }

三、输出

普通情况：略，参见分析部分

特殊情况：如果循环后还没有输出，说明无法包装，输出 -1 。

四、完整代码

#include <bits/stdc++.h>
using namespace std;
int n;
int main()
{
    cin >> n;
    for (int i = n / 5; i >= 0; i --)
        if ((n - i * 5) % 3 == 0)
        {
            cout << i + (n - i * 5) / 3;
            return 0;
        }
    cout << -1; //无法包装时
    return 0;
}

可以用f[i]表示i颗糖果最少的盒子数（inf表示无解），则f[i]=min(f[i-3],f[i-5])+1。初始状态为f[0]=0,f[1]=inf,f[2]=inf,f[3]=1,f[4]=inf。

f[0] = 0;
f[3] = 1;
for (int i = 5; i <= n; i++)
	f[i] = min(f[i - 3], f[i - 5]) + 1;
if (f[n] > 5000)
	cout << -1 << endl;
else
	cout << f[n] << endl;

结合易云老师的解析： 可以用f[i]表示i颗糖果最少的盒子数（inf表示无解），则f[i]=min(f[i-3],f[i-5])+1。初始状态为

f[0]=0；
f[1]=inf；
f[2]=inf；
f[3]=1；
f[4]=inf；

变量inf可以赋值为无穷大（0x3f3f3f3f）

完整代码

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int n,f[5000];
int main()
{
    cin>>n;
    f[0] = 0,f[1] = inf,f[2] = inf,f[3] = 1,f[4] = inf;
    for (int i = 5; i <= n; i++)
        f[i] = min(f[i - 3], f[i - 5]) + 1;
        if (f[n] > 5000)
            cout << -1 << endl;
        else
            cout << f[n] << endl;
    return 0;
}