DTOJ#5227. The Imp

DTOJ#5227. The Imp

传送门

你带着你自己挣得的一些金币来到了 Ye Olde 魔法商店，希望能买到一些有趣而不凡的魔法物品。商店里用特制的魔法盒子锁着 n n n 个物品，第 i i i 个箱子价格 c i c_i ci​ 个金币，包含着价值 v i v_i vi​ 个金币的物品。你知道并清楚的记得所有的 c i c_i ci​ 和 v i v_i vi​。

作为一个凡人，你最多只能携带一个魔法物品。因此你希望能得到最有价值的物品。你确实可以这么做，如果没有那个邪恶的魔法生物：小鬼的话。

小鬼可以使用一个魔法咒语，将魔法盒里的东西变成没有魔力和价值的灰尘。当然，它会在你已经购买了一个魔法盒子之后使用这个咒语，这样你就会付了钱却没得到东西。然后你就再买一个又一个…

小鬼的魔力足够他释放 k k k 次咒语，它也可以选择不使用它，允许你拿着这个物品，你可以在任何时候空着手离开（尽管这将成为一个耻辱）。但是，如果你拿到了一个物品，你就必须拿着它离开。你希望最大化你的收益（你获得的物品的价值减去你所花的所有的钱），而小鬼希望它最小。如果你们俩都绝顶聪明并且使用最佳策略，你将会获得多少金币的收益？

输入的第一行包括一个正整数 T T T 表示输入数据组数，每组数据的描述如下：

每组数据第一行有两个整数 n , k n,k n,k，含义如题面所示。

接下来的 n n n 行描述物品的性质，第 i i i 行包括两个整数 v i v_i vi​ 和 c i c_i ci​。

对于每一组数据，输出你所可能获得的最大收益。

样例输入

1
3 1
10 5
8 1
20 12

样例输出

7

对于 100 % 100% 100% 的数据，有 1 ≤ n ≤ 150000 , 1 ≤ k ≤ 9 , 0 ≤ v i , c i ≤ 1 0 6 1le nle 150000,1le kle 9,0le v_i,c_ile 10^6 1≤n≤150000,1≤k≤9,0≤vi​,ci​≤106。

2014-2015 ACM-ICPC, Central Europe Regional Contest (CERC 14)

题解：
首先证明性质：
对于确定的答案集合 a n s [ ] ans[] ans[]， a < b a<b a<b 则 v a < v b v_a<v_b va​<vb​。
证明：
考虑交换，即需满足 m i n ( v b − c b − v a , 0 ) + v a − c a > m i n ( v a − c a − v b , 0 ) + v b − c b min(v_b-c_b-v_a,0)+v_a-c_a>min(v_a-c_a-v_b,0)+v_b-c_b min(vb​−cb​−va​,0)+va​−ca​>min(va​−ca​−vb​,0)+vb​−cb​
拆开 m i n ( ) min() min()，即
①若 v b − c b − v a < 0 v_b-c_b-v_a<0 vb​−cb​−va​<0 且 v a − c a − v b < 0 v_a-c_a-v_b<0 va​−ca​−vb​<0，原式为 v b − c b − c a > v a − c a − c b v_b-c_b-c_a>v_a-c_a-c_b vb​−cb​−ca​>va​−ca​−cb​。当 v b − c b < v a < v b v_b-c_b<v_a<v_b vb​−cb​<va​<vb​ 时，显然成立。所以 v a < v b v_a<v_b va​<vb​。
②若 v b − c b − v a > 0 v_b-c_b-v_a>0 vb​−cb​−va​>0 且 v a − c a − v b < 0 v_a-c_a-v_b<0 va​−ca​−vb​<0，原式为 v a − c a > v a − c a − c b v_a-c_a>v_a-c_a-c_b va​−ca​>va​−ca​−cb​ 恒成立。而条件可推得 v a < v b − c b v_a<v_b-c_b va​<vb​−cb​。所以 v a < v b v_a<v_b va​<vb​
③若 v b − c b − v a < 0 v_b-c_b-v_a<0 vb​−cb​−va​<0 且 v a − c a − v b > 0 v_a-c_a-v_b>0 va​−ca​−vb​>0，原式为 v b − c a − c b > v b − c b v_b-c_a-c_b>v_b-c_b vb​−ca​−cb​>vb​−cb​ 即 c a < 0 c_a<0 ca​<0 恒不成立。当 v a < v b v_a<v_b va​<vb​ 时，条件显然不成立，所以不可能出现。
④若 v b − c b − v a > 0 v_b-c_b-v_a>0 vb​−cb​−va​>0 且 v a − c a − v b > 0 v_a-c_a-v_b>0 va​−ca​−vb​>0，原式为 v a − c a > v b − c b v_a-c_a>v_b-c_b va​−ca​>vb​−cb​。但是相加条件，为 c b + c a < 0 c_b+c_a<0 cb​+ca​<0 恒不成立。所以此情况不可能出现。
证毕。
于是我们把数按 v v v 递增排序，然后采用博弈 D P DP DP。
记 f [ i ] [ j ] f[i][j] f[i][j] 表示 后 i i i 个数，还剩 j j j 次操作的答案。
转移为 f [ i ] [ j ] = m a x ( f [ i + 1 ] [ j ] , m i n ( f [ i + 1 ] [ j − 1 ] − c i , v i − c i ) ) f[i][j]=max(f[i+1][j],min(f[i+1][j-1]-c_i,v_i-c_i)) f[i][j]=max(f[i+1][j],min(f[i+1][j−1]−ci​,vi​−ci​))
即不取，前面取过了和开始取。

#include<bits/stdc++.h>
#define N 150005
typedef long long ll;	
using namespace std;
inline ll read() {char ch;while(!isdigit(ch=getchar()));ll sum=ch^48;while(isdigit(ch=getchar()))sum=(sum<<1)+(sum<<3)+(ch^48);return sum;
}
struct node{ll v,c;
}a[N];
bool cmp(node x,node y){return x.v<y.v;}
ll f[N][10];
int main(){int T=read();while(T--){int n=read(),k=read();for(int i=1;i<=n;++i){a[i].v=read(),a[i].c=read();}sort(a+1,a+1+n,cmp);for(int j=0;j<=k;++j)f[n+1][j]=0;for(int i=n;i;--i){f[i][0]=max(f[i+1][0],a[i].v-a[i].c);for(int j=1;j<=k;++j){f[i][j]=max(f[i+1][j],min(a[i].v-a[i].c,f[i+1][j-1]-a[i].c));}}printf("%lldn",f[1][k]);}return 0;
}