hdu 4597 Play Game(记忆化搜索)

2024-06-05 03:38
文章标签 搜索 记忆 hdu game play 4597

本文主要是介绍hdu 4597 Play Game(记忆化搜索),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:hdu 4597 Play Game


题目大意:给出两堆牌,只能从最上和最下取,然后两个人轮流取,都按照自己最优的策略,问说第一个人对多的分值。


解题思路:记忆化搜索,状态出来就非常水,dp[fl][fr][sl][sr][flag],表示第一堆牌上边取到fl,下面取到fr,同样sl,sr为第二堆牌,flag为第几个人在取。如果是第一个人,dp既要尽量大,如果是第二个人,那么肯定尽量小。


#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int N = 25;
const int INF = 0x3f3f3f3f;
int n, f[N], s[N], dp[N][N][N][N][2];void init () {memset(dp, -1, sizeof(dp));scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d", &f[i]);for (int i = 1; i <= n; i++)scanf("%d", &s[i]);
}int solve (int fl, int fr, int sl, int sr, int flag) {int& ans = dp[fl][fr][sl][sr][flag];if (fl > fr && sl > sr)return ans = 0;if (ans != -1)return ans;if (flag) {ans = 0;if (fl <= fr) {ans = max(ans, solve(fl+1, fr, sl, sr, 1-flag) + f[fl]);ans = max(ans, solve(fl, fr-1, sl, sr, 1-flag) + f[fr]);}if (sl <= sr) {ans = max(ans, solve(fl, fr, sl+1, sr, 1-flag) + s[sl]);ans = max(ans, solve(fl, fr, sl, sr-1, 1-flag) + s[sr]);}} else {ans = INF;if (fl <= fr) {ans = min(ans, solve(fl+1, fr, sl, sr, 1-flag));ans = min(ans, solve(fl, fr-1, sl, sr, 1-flag));}if (sl <= sr) {ans = min(ans, solve(fl, fr, sl+1, sr, 1-flag));ans = min(ans, solve(fl, fr, sl, sr-1, 1-flag));}}return ans;
}int main () {int cas;scanf("%d", &cas);while (cas--) {init ();printf("%d\n", solve(1, n, 1, n, 1));}return 0;
}


这篇关于hdu 4597 Play Game(记忆化搜索)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1031965

相关文章

HTML5 搜索框Search Box详解

《HTML5搜索框SearchBox详解》HTML5的搜索框是一个强大的工具,能够有效提升用户体验,通过结合自动补全功能和适当的样式,可以创建出既美观又实用的搜索界面,这篇文章给大家介绍HTML5... html5 搜索框(Search Box)详解搜索框是一个用于输入查询内容的控件,通常用于网站或应用程

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

C# ComboBox下拉框实现搜索方式

《C#ComboBox下拉框实现搜索方式》文章介绍了如何在加载窗口时实现一个功能,并在ComboBox下拉框中添加键盘事件以实现搜索功能,由于数据不方便公开,作者表示理解并希望得到大家的指教... 目录C# ComboBox下拉框实现搜索步骤一步骤二步骤三总结C# ComboBox下拉框实现搜索步骤一这

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :