题目大意:小明过生日的时候,爸爸送给他一副乌龟棋当作礼物。乌龟棋的棋盘是一行 N个格子,每个格子上一个分数(非负整数)。棋盘第 1 格是唯一
的起点,第 N格是终点,游戏要求玩家控制一个乌龟棋子从起点出发走到终点。乌龟棋中 M 张爬行卡片,分成 4 种不同的类型(M 张卡片中不一定包含所有 4
种类型的卡片,见样例),每种类型的卡片上分别标有 1、2、3、4
四个数字之一,表示使用这种卡片后,乌龟棋子将向前爬行相应的格子数。游戏中,玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片,控制乌
龟棋子前进相应的格子数,每张卡片只能使用一次。游戏中,乌龟棋子自动获得起点格子的分数,并且在后续的爬行中每到达一个格子,就得到格子相应的分数。玩
家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。很明显,用不同的爬行卡片使用顺序会使得最终游戏的得分不同,小明想要找到一种卡片使用顺序使得最终游戏得分最多。现在,告诉你棋盘上每个格子的分数和所有的爬行卡片,你能告诉小明,他最多能得到多少分吗?
浓浓的DP气息~
状态:当前走在哪个位置,阶段:各种卡片已经用了几张,决策:下一张卡片使用哪种卡片。(代码实现时转化为上一张卡片用的哪一种)(个人这么认为。。可能有误。。)
我们设f[a][b][c][d]表示第一种、第二种、第三种、第四种卡片分别用了a,b,c,d张时能得到的最大分数。其中应该记录当前位置的那一维我们可以直接通过每种卡片使用的数量进行推算,所以省略掉,不然空间会炸。假设最后一步要用一张1类型卡片f[a][b][c][d]=f[a-1][b][c][d]+value[i]对于其他类型的卡片同理。然后在四种决策中选择得分最多的那种,即f[a][b][c][d]=max(f[a-1][b][c][d],f[a][b-1][c][d],f[a][b][c-1][d],f[a][b][c][d-1])这样f[a][b][c][d]即为答案。
预处理?——不需要~
noip2010-t2的更多相关文章
-
常规DP专题练习
POJ2279 Mr. Young's Picture Permutations 题意 Language:Default Mr. Young's Picture Permutations Time L ...
-
CH5E01 乌龟棋【线性DP】
5E01 乌龟棋 0x5E「动态规划」练习 描述 小明过生日的时候,爸爸送给他一副乌龟棋当作礼物.乌龟棋的棋盘是一行N 个格子,每个格子上一个分数(非负整数).棋盘第1 格是唯一的起点,第N 格是终点 ...
-
noip2010提高组题解
NOIP2010提高组题解 T1:机器翻译 题目大意:顺序输入n个数,有一个队列容量为m,遇到未出现元素入队,求入队次数. AC做法:直接开1000的队列模拟过程. T2:乌龟棋 题目大意:有长度为n ...
-
Noip2010提高组总结
将Noip2010重新做了一遍,第一遍做下来居然只有290分,比当年浙江的一等线低了20分,因为各种坏习惯丢掉了许多分数,Noip时需要特别注意! T1:机器翻译 第一题直接暴力,内存足够所以不用循环 ...
-
NOIP2010提高组真题部分整理(没有关押罪犯)
目录 \(NOIP2010\)提高组真题部分整理 \(T1\)机器翻译: 题目背景: 题目描述: 输入输出格式: 输入输出样例: 说明: 题解: 代码: \(T2\)乌龟棋 题目背景: 题目描述: 输 ...
-
洛谷 P1541 乌龟棋 &; [NOIP2010提高组](dp)
传送门 解题思路 一道裸的dp. 用dp[i][j][k][kk]表示用i个1步,j个2步,k个3步,kk个4步所获得的最大价值,然后状态转移方程就要分情况讨论了(详见代码) 然后就是一开始统计一下几 ...
-
[Noip2016]蚯蚓 D2 T2 队列
[Noip2016]蚯蚓 D2 T2 Description 本题中,我们将用符号[c]表示对c向下取整,例如:[3.0」= [3.1」=[3.9」=3.蛐蛐国最近蚯蚓成灾了!隔壁跳 蚤国的跳蚤也拿蚯 ...
-
T2 Func<;in T1,out T2>;(T1 arg)
委托调用方法的4种方式. using System; using System.Collections.Generic; namespace ConsoleApplication1 { delegat ...
-
Hotelling T2检验和多元方差分析
1.1 Hotelling T2检验 Hotelling T2检验是一种常用多变量检验方法,是单变量检验的自然推广,常用于两组均向量的比较. 设两个含量分析为n,m的样本来自具有公共协方差阵的q维正态 ...
-
NOIP2010提高组乌龟棋 -SilverN
题目背景 小明过生日的时候,爸爸送给他一副乌龟棋当作礼物. 题目描述 乌龟棋的棋盘是一行N个格子,每个格子上一个分数(非负整数).棋盘第1格是唯一的起点,第N格是终点,游戏要求玩家控制一个乌龟棋子从起 ...
随机推荐
-
tomcat 默认目录修改
引用:http://andrewyu.blog.51cto.com/1604432/544659 Tomcat7跟以前的版本一样,默认的发布程序是/usr/local/tomcat/webapps/R ...
-
PHP开发中的缓存技术汇总
在PHP开发中,出于对网站服务器负载的考虑,往往需要对页面.数据等内容进行缓存处理,下面就来看看,在PHP开发中有哪些缓存方式吧. 1.页面部分缓存该种方式,是将一个页面中不经常变的部分进行静态缓存, ...
-
第二天 Linux常见命令
复习: 判断题 1.fedora.redhat.Centos.suse.ubuntu.都是常见的linux 2./分区.swap分区./boot分区都是linux的必须分区 3./dev/sda5在l ...
-
Lua 5.1 参考手册
Lua 5.1 参考手册 by Roberto Ierusalimschy, Luiz Henrique de Figueiredo, Waldemar Celes 云风 译 www.codingno ...
-
AppServ的安装与配置
AppServ是一个软件集合,包括Apache(HTTP服务器软件).PHP(网页程序设计语言).MySQL(数据库管理系统软件).phpMyAdmin(图形界面的数据库管理软件)四个组成部分.App ...
-
获取地理位置的html5代码
/** * 以下为html5代码,获取地理位置 */ function getLocation() { //检查浏览器是否支持地理位置获取 if (navigator.geolocation) { / ...
-
ElasticSearch elasticsearch-servicewrapper 在linux上的安装部署全程记录
原文地址:http://www.cnblogs.com/tianjixiaoying/p/4316011.html 由于项目需求,需要在linux平台搭建一套ES服务.在搭建过程中,遇到各种各样的问题 ...
-
SQL SERVER 删除前判断指定的表或者存储过程是否存在
1.创建存储过程: CREATE PROCEDURE proc_pr ---将create修改成alter可以修改存储过程: AS BEGIN IF EXISTS(SELECT * FROM syso ...
-
Azure IoT Edge on Raspberry Pi 3 with Raspbian
在<Azure IoT Edge on Windows 10 IoT Core>一文中,我们以运行Windows 10 IoT Core的MinnowBoard MAX为例,详细讲述了Wi ...
-
Android-Chart
MPAndroidChart 包括折线图.曲线图.柱形图.饼图.K线图等等 我的地址:https://github.com/kongqw/MPAndroidChart 开源地址:https://git ...