HDU 4778 Gems Fight!(dp)

HDU 4778 Gems Fight!(dp)

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

HDU 4778 Gems Fight!

题目链接

题意:有n个背包,包里有一些宝石,如今爱丽丝和你轮流选背包,把包里宝石丢到锅中,然后假设锅中有宝石数量到s个,就会得到魔法石,而且能够继续选背包,两人都按最优策略去取,问最后两人魔法石会差多少。

思路:dp,dp[s]表示选背包状态为s时候的值,然后去记忆化搜索就可以,注意假设当前生成魔法石就继续加,否则就减就可以

代码:

#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;const int INF = 0x3f3f3f3f;const int N = 21;int g, b, s, dp[(1<<N) + 5], vis[(1<<N) + 5];int yu[(1<<N) + 5][10];struct Page {    int num;    int a[10];} p[N];int cal(int S, int u) {    int ans = 0;    for (int i = 1; i <= g; i++) {	ans += (yu[S][i] + p[u].a[i]) / s;    }    return ans;}int dfs(int now) {    int &tmp = dp[now];    if (vis[now]) return tmp;    vis[now] = 1;    tmp = 0;    int Min = INF, Max = -INF;    if (now == (1<<b) - 1) return tmp;    for (int i = 0; i < b; i++) {	if (now&(1<<i)) continue;	int sb = cal(now, i);	int next = (now|(1<<i));	if (sb != 0) {	    Max = max(Max, dfs(next) + sb);	}	else {	    Min = min(Min, dfs(next));	}    }    tmp = max(Max, -Min);    return tmp;}int main() {    while (~scanf("%d%d%d", &g, &b, &s) && g || b || s) {	for (int i = 0; i < b; i++) {	    memset(p[i].a, 0, sizeof(p[i].a));	    scanf("%d", &p[i].num);	    int tmp;	    for (int j = 0; j < p[i].num; j++) {		scanf("%d", &tmp);		p[i].a[tmp]++;	    }	}	for (int i = 0; i < (1<<b); i++) {	    vis[i] = 0;	    for (int j = 0; j < b; j++) {		if (i&(1<<j)) continue;		for (int k = 1; k <= g; k++) {		    yu[i|(1<<j)][k] = (yu[i][k] + p[j].a[k]) % s;		}	    }	}	printf("%d\n", dfs(0));    }    return 0;}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118659.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • jvisualvm 工具使用

    jvisualvm 工具使用转自:https://www.cnblogs.com/kongzhongqijing/articles/3625340.html jvisualvm工具使用 VisualVM是Netbeans的profile子项目,已在JDK6.0update7中自带(java启动时不需要特定参数,监控工具在bin/jvisualvm.exe)。&nbsp;https…

    2022年10月30日
  • 使用TinyXML读写xml文件

    使用TinyXML读写xml文件1、TinyXML  引用网上的原话:TinyXML是目前非常流行的一款基于DOM模型的XML解析器,简单易用且小巧玲珑,非常适合存储简单数据,配置文件,对象序列化等数据量不是很大的操作。支持对XML的读取和修改,不直接支持XPath,需要借助另一个相关的类库TinyXPath才可以支持XPath。  TinyXML源码是使用C++语言编写的,这对于C++应用来说是很好

  • 最全Pycharm教程(12)——Pycharm调试器之Java脚本调试

    最全Pycharm教程(12)——Pycharm调试器之Java脚本调试最全Pycharm教程(1)——定制外观  最全Pycharm教程(2)——代码风格  最全Pycharm教程(3)——代码的调试、运行  最全Pycharm教程(4)——有关Python解释器的相关配置  最全Pycharm教程(5)——Python快捷键相关设置  最全Pycharm教程(6)——将Pycharm作为Vim编辑器使用  最全Pyc

  • fastJson注解@JSONField指定字段的顺序「建议收藏」

    使⽤ordinal指定字段的顺序publicclassBasePackage{@JSONField(ordinal=1)privateintid;@JSONField(ordinal=2)privateintdirection;@JSONField(ordinal=3)privateStringtyp…

  • Jenkins前端打包内存溢出问题

    Jenkins前端打包内存溢出问题

  • Android ViewPager使用详解

    Android ViewPager使用详解这是谷歌官方给我们提供的一个兼容低版本安卓设备的软件包,里面包囊了只有在安卓3.0以上可以使用的api。而viewpager就是其中之一利用它,我们可以做很多事情,从最简单的导航,到页面菜单等等。那如何使用它呢,与LisstView类似,我们也需要一个适配器,他就是PagerAdapter。看一下api的图片, ViewPager的功能就是可以使视图滑动,就像Lanucher左右滑动那样。分三个步

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号