P4765 [CERC2014]The Imp 题解

· · 题解

首先，需要先得出一个结论，购买物品需要依照一个贪心的策略，购买的顺序需要按照 v_i 升序，证明如下。

设 v_1\le v_2，则依照升序的代价即 \min(v_1-c_1,v_2-c_1-c_2)，而如果交换两个物品，按照降序购买，代价则为 \min(v_2-c_2,v_1-c_1-c_2)，由于 v_1\le v_2，所以易得 v_1-c_1-c_2 \le \min(v_1-c_1,v_2-c_1-c_2)。证得，购买顺序应按照 v_i 升序进行。

之后便是 DP 的转移，可以发现，从最后一件商品向前转移更为简单，为了下标的方便，这里将 v_i 降序排列从 1 向 n 枚举转移。

设dp[i][j]，表示从 1 开始选到了 i，一共用了 j 次魔法。易得使用 0 次魔法时dp[i][0]=max(dp[i-1][0],v[i]-c[i])。

进行转移，可得dp[i][j]=max(dp[i-1][j],min(v[i]-c[i],dp[i-1][j-1]-c[i])。
分析这个转移方程，dp[i-1][j]意味着并不选 i 这件物品，min(v[i]-c[i],dp[i-1][j-1])表示小恶魔选取的更优秀的选项，即对于购买者更小的获利，其分别表示将 i 这件物品设为购买的最后一件、对购买的 i 物品使用魔法。最终答案为dp[n][k]。代码如下。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
    #define int long long
int read(){int d=1,k=0;char c=getchar();
while(!(c>='0' and c<='9' or c=='-'))c=getchar();if(c=='-')d=-1,c=getchar();
while(c>='0' and c<='9')k=(k<<3)+(k<<1)+(c^48),c=getchar();return d*k;}
int dp[200000][10],n,k;
struct node{int value,cost;}a[1000000];
int cmp(node x,node y){return x.value>y.value;}
signed main(){
    int T=read();
    while(T--){
        n=read(),k=read();
        for(int i=1;i<=n;i++)a[i].value=read(),a[i].cost=read();
        sort(a+1,a+1+n,cmp);
        for(int i=1;i<=n;i++)dp[i][0]=max(dp[i-1][0],a[i].value-a[i].cost);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=k;j++){
                dp[i][j]=max(dp[i-1][j],min(dp[i-1][j-1]-a[i].cost,a[i].value-a[i].cost));
            }
        }
        printf("%lld\n",dp[n][k]);
    } 
    return 0;
}