AtCoder R70 D No Need

题意:
给定$n$,$k$,再给定一个序列,定义好的集合是一个集合里所有的数之和大于等于$k$;序列如果序列中一个数$x$在所有包含它的好的子集中,去掉这个$x$这些子集也是好的,那么这个数就是不必要的数。求不必要的数的个数。

这个题好像很多提交是$\mathcal O(n)$水过的,然而我并不能证明这种贪心,所以记录一下$O(n^2logn)$的$dp$。

首先我们可以发现,如果一个数是不必要的,那么所有小于等于它的数也是不必要的。证明:如果一个数不必要,那么比他小的数可以代替它进入所有的子集,并且比他小的数被去掉后肯定和也大于$k$,所以这个数也不必要。

这样就会发现如果有$x$个数不必要,那么肯定是最小的$x$个数。

考虑二分,确定不必要的数有几个,然后进行$O(n^2)$的动态规划判断即可。如何判断这个数是否是必要的呢?如果去掉这个数$x$以后我们可以得到任意一个$[k-x,k)$的数,我们就能判断这个数不是不必要的,因为这表示至少存在一个子集是需要这个数的参与才能变为好的子集的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5000+5;
int n,k;
int a[maxn];
bool dp[maxn];
bool cal(int mid)
{
if(a[mid]>=k) return false;
memset(dp,0,sizeof(dp));
dp[0]=true;
for(int i=1;i<=n;i++)
{
if(i==mid) continue;
for(int j=k;j>=0;j--){
if(!dp[j]) continue;
if(j+a[i]<=k) dp[j+a[i]]=true;
}
}
for(int i=max(k-a[mid],0);i<k;i++)
if(dp[i]) return false;
return true;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+1+n);
int l=0,r=n;
while(r-l>0){
int mid=l+(r-l+1)/2;
if(cal(mid)) l=mid;
else r=mid-1;
}
printf("%d\n",l);
return 0;
}