题目:P2737
思路:
这题准确的说,是『布尔型完全背包』。
先打一遍板子,很容易。
int n;
scanf("%d", &n);
dp[0] = true;
for (int i = 1; i <= n; i++)
{
int a;
scanf("%d", &a);
for (int j = a; j <= ???; j++) dp[j] |= dp[j - a];
}
此处的 ???
即上界,这个过一会详细说明。
这题最棘手的地方有两个。
第一个是输出的处理。
如果仅仅需要输出:顾客不能用包装盒买到麦香牛块的最大块数
,那是非常容易的,使用这段代码即可:
for (int i = ???; i >= 0; i--)
if (dp[i] == false)
{
printf("%d", i);
return 0;
}
但是!!!题目还要求:
如果所有购买方案都能得到满足或者顾客不能买到的块数没有上限,输出 \(0\)。
我们再分两种情况解决。
-
如果所有购买方案都能得到满足,输出 \(0\)。
换句话说,全部 \(dp_i = true\)。
所以,我们只需要在程序末尾输出 \(0\) 即可(因为满足的情况已经被
return 0
了)。 -
如果顾客不能买到的块数没有上限,输出 \(0\)。
稍微有点复杂。这里就是第二个棘手的地方。
根据 『扩展欧几里德定理』,如果有不符合的数,必定会出现在 \(\max^{i=1}_{n}(a_i)^2\) 的范围里。
说白了就是 \(256 \times 256 = 65536\) 的范围里。
如果没有上限,说明范围内再加一个最大数也是不行的,即 \(65536\) 至 \(256 \times 257 = 65792\) 有数不符合。
那么代码就很简单了。
整体评价:
本题实现并不困难,在思路上有些难度。
绿题非常合理。
完整代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#define M 65536 //256*256
#define MM 65792 //256*257
using namespace std;
int dp[MM + 5];
int main()
{
int n;
scanf("%d", &n);
dp[0] = true;
for (int i = 1; i <= n; i++)
{
int a;
scanf("%d", &a);
for (int j = a; j <= MM; j++) dp[j] |= dp[j - a];
}
for (int i = M; i <= MM; i++)
if (dp[i] == false)
{
printf("0");
return 0;
}
for (int i = M-1; i >= 0; i--)
if (dp[i] == false)
{
printf("%d", i);
return 0;
}
printf("0");
return 0;
}
首发:2022-04-25 17:08:15
标签:练习题,输出,背包,return,int,完全,include,256,dp From: https://www.cnblogs.com/liangbowen/p/16622857.html