Problem's Link:

Mean:

n个物品，每个物品价值为v，价格为c，你只可以带一个物品离开。

有一个精灵，它可以施法让你购买后的物品价值变为0(未离开商店之前)，精灵最多施k次法术。

你的目的是让自己获得最大收益，而小鬼的目的正好相反。

如果你和精灵都采用最优策略，最后你可以盈利多少？

analyse:

第一感觉是三维dp，然而三维肯定会超时超内存。

然后就是想怎样压缩状态。。。

想了想其实两维就够了，为什么呢？因为对于第i件物品，如果我不选，那么它这次施不施法是没有影响的。

dp[i][j]：判断到第i个物品，精灵施了j次魔法，我还能获得的最大收益。

状态转移方程：dp[i][j]=max(dp[i-1][j],min(dp[i-1][j-1]-c,v-c))

伪代码：

for_each
i
{ 
if( 
select
i) 
{ 
for_each
j
{ 
if( 
magic
j
time) 
{ 
max( 
before
i) 
-
cost; 
}
else
{ 
value
-
cost; 
}
}
}
else
{ 
max( 
before
i); 
}
}

Time complexity: O(N*K)

Source code:

/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-15-12.09
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define  LL __int64
#define  ULL unsigned long long
using
namespace
std; 
const
LL
MAXN
=
200010; 
struct
node
{ 
LL
v
,
c; 
bool
operator
<( 
const
node
&
a) 
const
{ 
return
v
>
a
.
v; 
}
}
a
[
MAXN
];
LL
dp
[
MAXN
][
10
];
int
main() 
{ 
ios_base
::
sync_with_stdio( 
false); 
cin
.
tie( 
0); 
LL
Cas; 
scanf( 
"%I64d"
,
&
Cas); 
while( 
Cas
--) 
{ 
LL n 
,
k; 
scanf( 
"%I64d %I64d"
,
&n 
,
&
k); 
for( 
LL
i
=
1; 
i
<=n; 
++
i) 
{ 
scanf( 
"%I64d %I64d"
,
&
a
[
i
].
v
,
&
a
[
i
].
c); 
}
sort( 
a
+
1
,
a
+n 
+
1); 
LL
ans
=
0
,
val; 
memset( 
dp
,
0
,
sizeof
dp); 
for( 
LL
i
=
1; 
i
<=n; 
++
i) 
{ 
val
=
a
[
i
].
v
-
a
[
i
].
c; 
dp
[
i
][
0
]
=
max( 
dp
[
i
-
1
][
0
],
val); 
for( 
LL
j
=
1; 
j
<=
k; 
++
j) 
{ 
dp
[
i
][
j
]
=
max( 
dp
[
i
-
1
][
j
],
min( 
dp
[
i
-
1
][
j
-
1
]
-
a
[
i
].
c
,
val)); 
}
ans
=
max( 
ans
,
dp
[
i
][
k
]);
}
printf( 
"%I64d
\n
"
,
ans); 
}
return
0; 
}
/*
*/