文档章节

[NOIP2010] 乌龟棋 题解

o
 osc_isezqdgg
发布于 2019/09/18 15:52
字数 846
阅读 11
收藏 0
*j

精选30+云产品,助力企业轻松上云!>>>

题目描述:

乌龟棋的棋盘是一行NN个格子,每个格子上一个分数(非负整数)。棋盘第1格是唯一的起点,第NN格是终点,游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

乌龟棋中MM张爬行卡片,分成4种不同的类型(MM张卡片中不一定包含所有44种类型的卡片,见样例),每种类型的卡片上分别标有1,2,3,41,2,3,4四个数字之一,表示使用这种卡片后,乌龟棋子将向前爬行相应的格子数。游戏中,玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片,控制乌龟棋子前进相应的格子数,每张卡片只能使用一次。

游戏中,乌龟棋子自动获得起点格子的分数,并且在后续的爬行中每到达一个格子,就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。

很明显,用不同的爬行卡片使用顺序会使得最终游戏的得分不同,小明想要找到一种卡片使用顺序使得最终游戏得分最多。

现在,告诉你棋盘上每个格子的分数和所有的爬行卡片,你能告诉小明,他最多能得到多少分吗?

输入格式:

每行中两个数之间用一个空格隔开。

11行22个正整数N,MN,M,分别表示棋盘格子数和爬行卡片数。

22行NN个非负整数,a_1,a_2,…,a_Na1,a2,,aN,其中a_iai表示棋盘第ii个格子上的分数。

33行MM个整数,b_1,b_2,…,b_Mb1,b2,,bM,表示M张爬行卡片上的数字。

输入数据保证到达终点时刚好用光MM张爬行卡片。

题解:

我们发现只有4种卡片,并且使用某几种卡片就能确定下乌龟现在所在的位置。于是我们设f[i][j][k][l],表示使用了i张进1,使用了j张进2,使用了k张进3余使用了l张进4所能获得的最大分数。这个状态由上一次所在的位置转移过来。

附上代码:

#include<bits/stdc++.h>
using namespace std;
const int N=355,M=41;
int a[N],b[5],f[M][M][M][M];
int n,m;

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int i=1,l;i<=m;++i){
        scanf("%d",&l);
        b[l]++;
    }
    f[0][0][0][0]=a[1];
    for(int i=0;i<=b[1];++i){
        for(int j=0;j<=b[2];++j){
            for(int k=0;k<=b[3];++k){
                for(int l=0;l<=b[4];++l){
                    if(i-1>=0) f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+a[1+i+2*j+3*k+4*l]);
                    if(j-1>=0) f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]+a[1+i+2*j+3*k+4*l]);
                    if(k-1>=0) f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]+a[1+i+2*j+3*k+4*l]);
                    if(l-1>=0) f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]+a[1+i+2*j+3*k+4*l]);
                }
            }
        }
    }
    cout<<f[b[1]][b[2]][b[3]][b[4]];
    return 0;
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
[Noip2010]乌龟棋

小明过生日的时候,爸爸送给他一副乌龟棋当作礼物。乌龟棋的棋盘是一行N个格子,每个格子上一个分数(非负 整数)。棋盘第1格是唯一的起点,第N格是终点,游戏要求玩家控制一个乌龟棋子从起点...

osc_uhmvp9bs
2018/08/08
2
0
noip2010 乌龟棋

题目描述 乌龟棋的棋盘是一行N个格子,每个格子上一个分数(非负整数)。棋盘第1格是唯一的起点,第N格是终点,游戏要求玩家控制一个乌龟棋子从起点出发走到终点。 乌龟棋中M张爬行卡片,分成...

osc_z7d2bxvl
2019/01/30
1
0
NOIP 2010 乌龟棋

P1541 乌龟棋 题目背景 小明过生日的时候,爸爸送给他一副乌龟棋当作礼物。 题目描述 乌龟棋的棋盘是一行 NN 个格子,每个格子上一个分数(非负整数)。棋盘第1格是唯一的起点,第 NN 格是终...

osc_ryjlu6z2
2018/07/16
0
0
7-22 龟兔赛跑

7-22 龟兔赛跑(20 分) 乌龟与兔子进行赛跑,跑场是一个矩型跑道,跑道边可以随地进行休息。乌龟每分钟可以前进3米,兔子每分钟前进9米;兔子嫌乌龟跑得慢,觉得肯定能跑赢乌龟,于是,每跑...

osc_n50eizn7
2018/04/07
0
0
乌龟棋 洛谷1541

题目 乌龟棋的棋盘是一行N个格子,每个格子上一个分数(非负整数)。棋盘第1格是唯一的起点,第N格是终点,游戏要求玩家控制一个乌龟棋子从起点出发走到终点。 乌龟棋中M张爬行卡片,分成4种...

a_loud_name
2018/04/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

阻塞锁,非阻塞锁,自旋锁,互斥锁

1.阻塞锁 多个线程同时调用同一个方法的时候,所有线程都被排队处理了。让线程进入阻塞状态进行等待,当获得相应的信号(唤醒,时间) 时,才可以进入线程的准备就绪状态,准备就绪状态的所有...

osc_umiwij2c
18分钟前
5
0
Asp.NetCore3.1 WebApi中模型验证

前言   不管是前端,还是后端,做数据合法性验证是避免不了的,这边文章就记录一下Asp.NetCore3.1 WebApi中的模型验证; 传统写法--不使用模型验证   来,先上图:   我相信,应该绝大...

osc_qgfjs4a5
19分钟前
21
0
龙芯开源社区上线.NET主页

龙芯团队从2019年7 月份开始着手.NET Core的MIPS64支持研发,经过将近一年的研发,在2020年6月18日完成了里程碑性的工作,在github CoreCLR 仓库:https://github.com/gsvm/coreclr, 随后受...

osc_bj12kvua
20分钟前
11
0
高并发下浏览量入库设计

一、背景 文章浏览量统计,low的做法是:用户每次浏览,前端会发送一个GET请求获取一篇文章详情时,会把这篇文章的浏览量+1,存进数据库里。 1.1 这么做,有几个问题: 在GET请求的业务逻辑里...

osc_uj3h5gt9
21分钟前
27
0
nginx timeout 配置 全局timeout 局部timeout web timeout

nginx比较强大,可以针对单个域名请求做出单个连接超时的配置. 比如些动态解释和静态解释可以根据业务的需求配置 proxy_connect_timeout :后端服务器连接的超时时间_发起握手等候响应超时时间...

osc_5cok9i01
23分钟前
11
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部