Cut Ribbon
基本思路
一眼完全背包，然而样例全过却无法AC。
看了提示之后明白这是一个要求必须完全装满的完全背包。
意思就是纸带剪完的剩余也得是要求的长度。
我一开始的想法是打标记，所有非要求长度的都标记成负数，然后要求长度的F数组设为1。
for (int i = 0; i <= 5010; i++)
{
F[i] = -100000;
}
for (int i = 1; i <= 3; i++)
{
F[v[i]] = 1;
}
for (int i = 1; i <= 3; i++)
{
for (int j = v[i]; j <= n; j++)
{
F[j] = max(F[j], F[j - v[i]] + 1);
}
}
然而这是可以证伪的。
因为这只标记了要求长度的一倍，当要求长度的\(n\)倍，或者两个要求长度的线性组合出现时都是被标记成负一的，除非同步更新标记。
然而我并没有想到怎么同步更新标记。
题解思路
实际上也是标记。
但是巧妙地通过状态转移方程来更新了。
首先把所有点打上\(-1\)标记。
然后只给\(F[0]\)赋值为\(0\)
之后标记的更新就交给了转移方程。
for (int i = 1; i <= 3; i++)
{
for (int j = v[i]; j <= n; j++)
{
if (F[j - v[i]] != -1)
F[j] = max(F[j], F[j - v[i]] + 1);
}
}
这个过程很巧妙的避免了背包不满的情况。
写到一半冲去西二英语课点名了
具体地，比如第一轮更新时肯定只能更新到\(F[0] \neq - 1\)的状况，也就是更新了第一个物品的状态和标记。
第二轮则只能从刚好装满第一个物品的状态下转移。
以此类推。
代码实现
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int n;
int v[4];
int F[5010];
int main()
{
cin >> n;
cin >> v[1] >> v[2] >> v[3];
for (int i = 0; i <= 5010; i++)
{
F[i] = -1;
}
F[0] = 0;
for (int i = 1; i <= 3; i++)
{
for (int j = v[i]; j <= n; j++)
{
if (F[j - v[i]] != -1)
F[j] = max(F[j], F[j - v[i]] + 1);
}
}
cout << F[n];
return 0;
}