【洛谷】P1541 乌龟棋(四维背包dp)
题目背景
小明过生日的时候,爸爸送给他一副乌龟棋当作礼物。
题目描述
乌龟棋的棋盘是一行N个格子,每个格子上一个分数(非负整数)。棋盘第1格是唯一的起点,第N格是终点,游戏要求玩家控制一个乌龟棋子从起点出发走到终点。
乌龟棋中M张爬行卡片,分成4种不同的类型(M张卡片中不一定包含所有4种类型的卡片,见样例),每种类型的卡片上分别标有1、2、3、4四个数字之一,表示使用这种卡片后,乌龟棋子将向前爬行相应的格子数。游戏中,玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片,控制乌龟棋子前进相应的格子数,每张卡片只能使用一次。
游戏中,乌龟棋子自动获得起点格子的分数,并且在后续的爬行中每到达一个格子,就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。
很明显,用不同的爬行卡片使用顺序会使得最终游戏的得分不同,小明想要找到一种卡片使用顺序使得最终游戏得分最多。
现在,告诉你棋盘上每个格子的分数和所有的爬行卡片,你能告诉小明,他最多能得到多少分吗?
输入输出格式
输入格式:
输入文件的每行中两个数之间用一个空格隔开。
第1行2个正整数N和M,分别表示棋盘格子数和爬行卡片数。
第2行N个非负整数,a1a2……aN,其中ai表示棋盘第i个格子上的分数。
第3行M个整数,b1b2……bM,表示M张爬行卡片上的数字。
输入数据保证到达终点时刚好用光M张爬行卡片。
输出格式:
输出只有1行,1个整数,表示小明最多能得到的分数。
输入输出样例
9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1
73
说明
每个测试点1s
小明使用爬行卡片顺序为1,1,3,1,2,得到的分数为6+10+14+8+18+17=73。注意,由于起点是1,所以自动获得第1格的分数6。
对于30%的数据有1≤N≤30,1≤M≤12。
对于50%的数据有1≤N≤120,1≤M≤50,且4种爬行卡片,每种卡片的张数不会超过20。
对于100%的数据有1≤N≤350,1≤M≤120,且4种爬行卡片,每种卡片的张数不会超过40;0≤ai≤100,1≤i≤N;1≤bi≤4,1≤i≤M。
-------------------------------------------------------------------------------------------------
分析:我自带buff:眼瞎,没看到卡片上的数字只有1-4,死活不会(估计看到了也不会)。
其实这是个背包dp
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=,maxm=;
int dp[][][][],a[maxn],cnt[];
int main()
{
int n,m,x;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=m;i++)
{
scanf("%d",&x);
cnt[x]++;
}
for(int i=;i<=cnt[];i++)
for(int j=;j<=cnt[];j++)
for(int k=;k<=cnt[];k++)
for(int l=;l<=cnt[];l++)
{
dp[i][j][k][l]
=max(
max( dp[max(i-,)][j][k][l], dp[i][max(j-,)][k][l] ),
max( dp[i][j][max(k-,)][l], dp[i][j][k][max(l-,)] )
);
dp[i][j][k][l]+=a[+i+*j+*k+*l];
}
printf("%d",dp[cnt[]][cnt[]][cnt[]][cnt[]]);
return ;
}
解决【洛谷】P1541 乌龟棋,打卡
最新文章
- linux环境初始化 用户问题
- du 使用详解 linux查看目录大小 linux统计目录大小并排序 查看目录下所有一级子目录文件夹大小 du -h --max-depth=1 |grep [
- sql server 根据执行计划查询耗时操作
- PHP中strtotime函数使用方法分享
- javascript——操作符(~、&;、|、^、<;<;、>;>;)
- 如何关闭浏览器的HSTS功能
- IT经典书籍——Head First系列…
- HDU - 1241 dfs or bfs [kuangbin带你飞]专题一
- Head First Servlet and JSP
- 【安全性测试】一个简单地绕前端暴XSS漏洞
- 微信小程序 table 简单测试
- 05-RARP: 逆地址解析协议
- 十五分钟介绍 Redis数据结构
- 申请LINE 帐号的所有方法
- ActiveMQ 使用场景
- 十一、springboot之web开发之Filter
- CI框架中site_url()和base_url()的区别
- 【XPath Helper:chrome爬虫网页解析工具 Chrome插件】XPath Helper:chrome爬虫网页解析工具 Chrome插件下载_教程_安装 - 开发者插件 - Chrome插件网
- appium自动化环境搭建
- Linux性能工具