算法
DP。
用$f[i][j][k]$表示前i张卡片抽j张能否打出k。
注意到i最后是不需要的,可以压掉这一维。
状态转移方程即为$f[j]|=f[j-1]<<x[i]$,同时x也可以不开。
可以使用bitset来保存。
然后计算一下$t=0$时m的最小值和最大值即可。
代码
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <bitset>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
return X*w;
}
const int N=260;
const int M=75010;
const int INF=214748364;
int n,k,a,b;
bitset<M> f[N];
int l[M],r[M];
int main() {
n=read(),k=read(),a=read(),b=read();
f[0].set(0);
int Sum=0;
for (re int i=1;i<=n;i++) {
int x=read();
for (re int j=k;j;j--)
f[j] |= f[j-1] << x;
Sum+=x;
}
l[a]=-INF;
for (re int i=a;~i;i--)
if (f[k][i]) { l[a]=i; break; }
for (re int i=a+1;i<=b;i++)
if (f[k][i]) l[i]=i;
else l[i]=l[i-1];
r[b]=INF;
for (re int i=b;i<=Sum;i++)
if (f[k][i]) { r[b]=i; break; }
for (re int i=b-1;i>=a;i--)
if (f[k][i]) r[i]=i;
else r[i]=r[i+1];
int ans=-INF;
for (re int i=a;i<=b;i++) ans=max(ans,min(i-l[i],r[i]-i));
printf("%d\n",ans);
return 0;
}