J.溪染的优惠券(贪心01背包)

LINK

有点像 $01$ 背包,但是又不完全是

原因在于使用的物品有限制,使得物品的使用次序是未知的

这样显然无法扫一遍做 $01$ 背包

如果按照 $a_i$ 排序也是不对的,限制大的不一定先使用

若使用变为 $k-b_i$ ,这样中间错过了许多小型优惠劵,可能先使用中间的才更优

于是想到按照 $a_i-b_i$ 排序,直接做 $01$ 背包即可.

这样选择物品的顺序满足 $a_i-b_i>a_j-b_j$

如果只选择 $i,j$ 优惠券中的一个,那么顺序是无所谓的, $01$ 背包会考虑到

如果需要同时选择 $i,j$ 物品,那么按照 $i,j$ 的顺序 $dp$ 一定是可行的

反证法

设按照 $j,i$ 的顺序选可行得到 $k>=a_j\&\&k-b_j>=a_i$

按照 $i,j$ 顺序选优惠券不可行得到 $k>=a_i\&\&k-b_i<a_j$

我们得到 $k>=a_i+b_j\&\&k<a_j+b_i$ ,也就是 $a_j+b_i>a_i+b_j$

而因为 $a_i-b_i>a_j-b_j$ ,移项得到 $a_i+b_j>a_j+b_i$

显然矛盾,证毕,不存在这种情况.

也就是说,按照 $i,j$ 这种方式排序不会错,直接做 $01$ 背包即可

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4+10;
int n,k,vis[maxn],s[maxn],f[maxn];
typedef pair<int,int>p;
p a[maxn];
bool com(p a,p b)
{
    if( a.first-a.second==b.first-b.second )    return a.first<b.first;
    return a.first-a.second>b.first-b.second;
}
int main()
{
    cin >> n >> k;
    for(int i=1;i<=n;i++)    cin >> a[i].first >> a[i].second;
    f[k] = 1;
    sort( a+1,a+1+n,com );
    for(int i=1;i<=n;i++)
    for(int j=a[i].first;j<=k;j++)
        f[j-a[i].second] |= f[j];
    int ans = k;
    for(int i=0;i<=k;i++)
        if( f[i] ){    cout << i; return 0; }
}