P4765 [CERC2014]The Imp（博弈dp）

本文主要是介绍P4765 [CERC2014]The Imp（博弈dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
你用一些辛苦赚来的黄金来到魔术商店，去购买奇妙而独特的魔法物品。商店里有这样的物品，每一个都锁在一个特殊的魔术箱里。我的TI thi盒的成本CICI ICI黄金碎片购买，并包含一个项目价值ViViVi黄金碎片。成本和项目价值是众所周知的，正如你以前阅读、掌握和记忆Yelod魔术目录一样。

一个凡人，比如你，可以安全地携带一个魔法物品。因此，你的目标是得到最珍贵的。如果你不是一个邪恶的魔法生物，你就会得到它。

小鬼可以施放恶作剧的咒语，它将任何魔法盒子的内容转化成毫无价值的尘埃。当然，他会在你买一个盒子后使用这个咒语，让你为这个物品付钱，而不是得到它。你被迫购买另一个盒子，然后是下一个盒子…

小鬼有足够的魔力在大多数KKK时间施放魔法。当然，他可以避免使用它，让你保留一个项目。你可以随时走开，两手空空（虽然肯定是耻辱）。然而，如果你得到一个项目，你必须保持它离开商店。

你的目标是使你的收益最大化（所获得的项目减去以前支付的所有费用），而IMP则希望最小化它。如果你和生物都使用最佳策略，你会赚多少黄金？

参考自：https://blog.csdn.net/weizhuwyzc000/article/details/48183793
思路：
对于博弈dp，因为双方都是最优的，所以双方都得利用dp方程。
定义$dp[i][j]$为从第$i$个物品开始选，小鬼还可以使用$j$次膜法，我所能得到的最大价值。

那么转移方程就是$dp[i][j]=max(v,dp[i+1][j])$，
$dp[i+1][j]$代表不选这个物品的所得,$v$代表选这个物品的所得

则$v=min(dp[i+1][j-1]-a[i].c,a[i].v-a[i].c)$，代表我选择这个物品时，小鬼干扰和不干扰，我能得到的值。

但是本题需要按照价值进行排序。因为假设你都选了k个物品的时候，价值为
$a[x].v-a[x1].c-a[x2].c-a[x3].c...$
很明显选定相同的k个物品时候（也就是小鬼施行了k-1次膜法），a[x].v的值越大，相对越优。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>using namespace std;
typedef long long ll;const int maxn = 2e5 + 7;
const int INF = 0x3f3f3f3f;
int dp[maxn][10],vis[maxn][10];
int n,k;struct Node {int v,c;bool operator < (const Node &rhs) const {return v < rhs.v;}
}a[maxn];int DP(int i,int j) {if(i == n + 1) return 0;if(vis[i][j]) return dp[i][j];vis[i][j] = 1;int v = a[i].v - a[i].c; //当前这一局选能得到的最大值if(j > 0) v = min(v,DP(i + 1,j - 1) - a[i].c);//小鬼选不选dp[i][j] = max(DP(i + 1,j),v); //我选不选return dp[i][j];
}void init() {for(int i = 1;i <= n;i++) {for(int j = 0;j <= 9;j++) {dp[i][j] = -INF;vis[i][j] = 0;}}
}int main() {int T;scanf("%d",&T);while(T--) {init();scanf("%d%d",&n,&k);for(int i = 1;i <= n;i++) {scanf("%d%d",&a[i].v,&a[i].c);}sort(a + 1,a + 1 + n);printf("%d\n",DP(1,k));}return 0;
}

这篇关于P4765 [CERC2014]The Imp（博弈dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---