[NOIP2010 提高组] 乌龟棋

news/2025/2/14 16:38:09/

题意:给你一个一维棋盘,棋盘上有对应的分数,然后给你若干张牌,每张牌的数字代表它可以使小乌龟移动的距离(1,2,3,4)给定的牌必须全部消耗完且最后一定可以到达终点,询问可以获得的最大的分数?

分析:首先这个题很容易陷入对棋盘进行DP的错误思路,其实这里的思路是开4维DP,

DP【i】【j】【k】【m】:在消耗(1,2,3,4)牌的数目分别是(i,j,k,m)的情况下

我们获得的最大的分数,显然答案就是DP【cnt[1]】【cnt[2]】【cnt[3]】【cnt[4]】

那么状态如何更新呢?

发现:我们消耗的牌的数目决定了我们当前在哪一格

t  = i*1+j*2+k*3+m*4+1 就是我们当前所处的位置

当前状态最后一个不同的递推点在于选择权值多大的牌来使用,例如

if(i) DP【i】【j】【k】【m】= max(DP[i][j][k][m],DP[i-1][j][k][m]+w[t]);

....同理可得出替其他的

注意还需要初始化一下我们的DP【0】【0】【0】【0】 = w【1】;

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
ll n,m;
ll w[N];
ll cnt[10];
ll f[45][45][45][45];
int main(){cin>>n>>m;for(int i=1;i<=n;i++)cin>>w[i];while(m--){int a;cin>>a;cnt[a]++;}f[0][0][0][0] = w[1];for(ll a=0;a<=cnt[1];a++)for(ll b=0;b<=cnt[2];b++)for(ll c=0;c<=cnt[3];c++)for(ll d=0;d<=cnt[4];d++){ll t=a*1+b*2+c*3+d*4+1;ll &tem = f[a][b][c][d];if(a)tem = max(tem,f[a-1][b][c][d]+w[t]);if(b)tem = max(tem,f[a][b-1][c][d]+w[t]);if(c)tem = max(tem,f[a][b][c-1][d]+w[t]);if(d)tem = max(tem,f[a][b][c][d-1]+w[t]);}cout<<f[cnt[1]][cnt[2]][cnt[3]][cnt[4]];}

还是欠缺知识,慢慢积累吧,成功在于不懈的积累,学到这里发现,信息学和数学很大的不一样的地方在于,它很难有统一的现成模式(通法)直接套用,它需要见大量的习题来积累经验,这需要非常大的抵抗这种困难的毅力。


http://www.ppmy.cn/news/856364.html

相关文章

ROS小乌龟

环境准备 ubuntu20.04 ROS 步骤 ctrlaltT开启新窗口 输入上述命令后&#xff0c;会出现下图所示的窗口 启动键盘控制

乌龟棋

1. 子问题描述&#xff1a;用dp[i][j][x][y] 表示当4种卡片剩余量分别是i,j,x,y 的时候&#xff0c;获得的最大积分。&#xff08;设4种卡片总量分别为a,b,c,d&#xff09; 2. 状态迁移方程&#xff1a;dp[i][j][x][y]max(dp[i1][j][x][y], dp[i][j1][x][y], dp[i][j][x1][y], …

捉乌龟的游戏

甲乙二人玩捉乌龟的游戏&#xff0c;先将一付54张扑克牌&#xff08;27对&#xff09;藏起一张&#xff0c;于是剩下的牌中必有一张没有对子&#xff0c;称为“乌龟”&#xff0c;再将牌分给两个人&#xff0c;每个人将自己手中的对子全部扔掉&#xff0c;这时你能否根据两人手…

小乌龟 检出项目代码

1 SVN Checkout: 不脱离svn导出代码(桌面右键) 不能拷贝给其他人 注&#xff1a;导出位置最后要加上\ 2 TortoiseSVN-->Export: 脱离svn导出代码(桌面右键) 导出的代码可以直接导入eclipse中 转载于:https://www.cnblogs.com/Alan0218/articles/8466847.html

【开发环境搭建之Gitee+小乌龟】

Gitee代码托管小乌龟可视化界面加小乌龟汉化 第一步 下载资源 点击下载【Gitee小乌龟】 第二步 安装软件GItee 资源下载后解压&#xff0c;双击打开Git-2.33.0.2-64-bit.exe&#xff0c;然后无脑下一步&#xff0c;下一步&#xff0c;安装就可以了。可以改下安装路径&#…

认识一下小龟机器人主控板

简要 小龟机器人主控板采用乐鑫ESP32处理器&#xff0c;总共有23组可控制管脚&#xff0c;所以最多支持23个舵机、4个电机、10根可输入输出编程管脚、23根管脚全部支持输出控制。 正面插口说明 电源区 5V电源插口 由两枚2.54mm排针组成&#xff0c;需要使用5V电源的传感器模…

NOIP201006乌龟棋 题解

NOIP201006乌龟棋 题解 题目链接字面描述题目背景题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示 思路状态定义状态转移方程状态初始化 代码实现 题目 链接 https://www.luogu.com.cn/problem/P1541 字面描述 题目背景 小明过生日的时候&#xff0c;爸爸送给…

巴西龟饲养日志----巴西龟成长标志

养了半年巴西龟&#xff0c;从刚出壳到长到如今这么大&#xff0c;确实不容易,阵亡了四只&#xff0c;毕竟是要交学费的&#xff0c;目前还有9只&#xff0c;状态还不错。 养了这么久&#xff0c;龟长这么大&#xff0c;突然就发现巴西龟成长的标志了。 首先最能发现的地方就…