P2737 [USACO4.1]麦香牛块Beef McNuggets

题目传送门：P2737 [USACO4.1]麦香牛块Beef McNuggets

简化题意：其实就是给你 n n n 个数， a 1 a_1 a1​ 到 a n a_n an​ ，对于每个数取任意个，把它们的和放到集合 S S S 中，找出在集合 S S S 中最大的正整数 x x x ，使得 $x \not \in S $

这题大概思路就是确定两个范围，设有两数 m ,   r m,\ r m, r，它们满足：

所有的测试点里的答案 ≤ m \le m ≤m

如果凑出来的数有上限，那么 { x ∣ x ∈ [ r , m ] , x ∈ N + } ⊆ S \{x \mid x \in [r,m],x \in N+\} \subseteq S {x∣x∈[r,m],x∈N+}⊆S

反之 { x ∣ x ∈ [ r , m ] , x ∈ N + } ⊈ S \{x \mid x \in [r,m],x \in N+\} \not\subseteq S {x∣x∈[r,m],x∈N+}​⊆S

我们先假设 m   r m\ r m r 存在，那么我们要确定的就是在 [ r , m ] [r,m] [r,m] 范围内的每一个正整数能否被凑出来

这怎么求呢，很明显这是一个布尔型完全背包模板

代码：

f[0]=true;
for(int i=1;i<=n;i++)
	for(int j=a[i];j<=M;j++)//即前文中的m
		f[j]|=f[j-a[i]];
           

没看懂的话建议百度完全背包

前方高能

确定 m   r m\ r m r，我们发现前面的背包时间复杂度是 O ( n m ) O(nm) O(nm) 如果这个算法能过的话，应该满足 n m ≤ 1 0 8 nm \le 10^8 nm≤108 其中 n ≤ 10 n \le 10 n≤10，那么 m ≤ 1 0 7 m \le 10^7 m≤107 时 m m m 一定满足上述条件，于是我们设 m = 1 0 7 m=10^7 m=107 ,那么如何确定 r r r 呢？这个数不好靠分析时间复杂度的方式来算，于是我干脆蒙了一个数 r = 5 × 1 0 6 r=5 \times 10^6 r=5×106 ，然后对了！

献上代码:

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int NR=15, MR=1e7, LYGXMD=5e6;
//LYGXMD代表R, MR代表M
int n, a[NR], f[MR+10];
int main()
{
	//输入
	scanf("%d", &n);
	for(int i=1;i<=n;i++)
		scanf("%d", a+i);
	//背包
	f[0]=true;
	for(int i=1;i<=n;i++)
		for(int j=a[i];j<=MR;j++)
			f[j]|=f[j-a[i]];
	//找到没有上限的情况
	for(int i=LYGXMD;i<=MR;i++)
		if(!f[i])
		{
			printf("0");
			return 0;
		}
	//算出答案
	int ans=MR;
	while(ans>0 && f[ans])ans--;
   //如果有答案的话那么输出答案
	printf("%d", ans);
	return 0;
}
           

当然我的用时间复杂度分析的方法不是正解，但却是比赛中很实用的技巧，至于 m   r m\ r m r正解的算法可以看看别的题解， dalao 们解释的都很清楚