洛谷 P1541 [NOIP2010 提高组] 乌龟棋

2024-04-27 04:12

本文主要是介绍洛谷 P1541 [NOIP2010 提高组] 乌龟棋,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

思路:暴力DP‘“

其实在想到暴力dp之前,作者寻思着这个题目可能和”摆花“那道题差不多,就用那种思想想了一下,结果其实不是这样的。这里并不能开二维进行推进。由于我们在二维表示的时候,代表的含义就是在走了i个格子用了j个票子所积累到的最大积分。

其实DP思路上看起来是没有什么错误的,但是呢,我这里忽略掉了:这里的票子是分种类的,也就是说,这里的票子并不是自由选的,我们必须保证这个票子正好用完,并且每一种票子是用一次的,并不能重复使用。这里可以用01背包的思路,但是呢,我们还需要保证它走的路数正好和票数是对上的,也就是票数必须是正好才行,在这种情况下求最大价值。我们如果用01背包那种思想,其实就是在用完n张票子之前就已经选中了最佳的情况,但是不一定就是正好用完五张票子最大的价值,可能是我们在遍历过程中重复使用票子得到的结果,而我们在这样的情况下并不能进行约束。所以我们需要换一种思想。

后来,可以发现我们需要用这种暴力的方法来做。这样暴力的话很好懂了。

四维数组开起来之后,我们就直接专心应对所需要的卡片数进行比较就行了,加上我们走到这个当前格子的积分求出来最大值就行了。

注意:在求最大积分的时候,我们不要忘记在不用任何票子的时候我们的状态是第一个格子的积分,因为我们总是从这个起点开始走。好了,还有一点就是我们在转移的时候,加上格子积分的时候我们需要额外+1.也就是+1+a*1+b*2+c*3+d*4.为什么呢?因为我们在前面已经加上第一个格子的积分了,所以我们不能再从1开始加了,这样的话不仅很难发现错误,并且还会导致结果错。

上代码:

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath> 
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<deque>
#include <iomanip>
#include<sstream>
#include<numeric>
#include<map>
#include<limits.h>
#include<unordered_map>
#include<set>
#define int long long
#define MAX 4400
#define inf 0x3f3f3f3f
#define _for(i,a,b) for(int i=a;i<(b);i++)
using namespace std;
typedef pair<int, int> PII;
int n,m;
int counts;
int dx[] = { 0,1,0,-1};
int dy[] = { 1,0,-1,0 };
int arr[MAX];
int piao[MAX];
int dp[50][50][50][50];
signed main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> arr[i];}dp[0][0][0][0] = arr[1];for (int i = 1; i <= m; i++) {int x;cin >> x;piao[x]++;}for (int a = 0; a <= piao[1]; a++) {for (int b = 0; b <= piao[2]; b++) {for (int c = 0; c <= piao[3]; c++) {for (int d = 0; d <= piao[4]; d++) {int r = 1 + a * 1 + b * 2 + c * 3 + d * 4;if (a != 0) dp[a][b][c][d] = max(dp[a - 1][b][c][d]+arr[r], dp[a][b][c][d]);if (b != 0)dp[a][b][c][d] = max(dp[a][b - 1][c][d]+arr[r], dp[a][b][c][d]);if (c != 0)dp[a][b][c][d] = max(dp[a][b][c - 1][d]+arr[r], dp[a][b][c][d]);if (d != 0)dp[a][b][c][d] = max(dp[a][b][c][d], dp[a][b][c][d - 1]+arr[r]);}}}}cout << dp[piao[1]][piao[2]][piao[3]][piao[4]];return 0;
}

这篇关于洛谷 P1541 [NOIP2010 提高组] 乌龟棋的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/939493

相关文章

uva 10154 DP 叠乌龟

题意: 给你几只乌龟,每只乌龟有自身的重量和力量。 每只乌龟的力量可以承受自身体重和在其上的几只乌龟的体重和内。 问最多能叠放几只乌龟。 解析: 先将乌龟按力量从小到大排列。 然后dp的时候从前往后叠,状态转移方程: dp[i][j] = dp[i - 1][j];if (dp[i - 1][j - 1] != inf && dp[i - 1][j - 1] <= t[i]

键盘快捷键:提高工作效率与电脑操作的利器

键盘快捷键:提高工作效率与电脑操作的利器 在数字化时代,键盘快捷键成为了提高工作效率和优化电脑操作的重要工具。无论是日常办公、图像编辑、编程开发,还是游戏娱乐,掌握键盘快捷键都能带来极大的便利。本文将详细介绍键盘快捷键的概念、重要性、以及在不同应用场景中的具体应用。 什么是键盘快捷键? 键盘快捷键,也称为热键或快捷键,是指通过按下键盘上的一组键来完成特定命令或操作的方式。这些快捷键通常涉及同

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 (最大值之和)给定整数序列 a0,⋯,an−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr(其中0≤l≤r<n0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同,当且仅当下标不同。 例如,当原序列为 [1,2,1,2] 时,要计算子序列 [

如何提高 GitHub 的下载速度

如何提高 GitHub 的下载速度 文章目录 如何提高 GitHub 的下载速度1. 注册账号2. 准备好链接3. 创建仓库4. 在码云上下载代码5. 仓库更新了怎么办 一般来说,国内的朋友从 GitHub 上面下载代码,速度最大是 20KB/s,这种龟速,谁能忍受呢? 本文介绍一种方法——利用“码云”,可以大大提高下载速度,亲测有效。 1. 注册账号 去“码云”注册一

如何提高开发的效率,让老板不知所措的给你发工资

设计模式 UML JSP 编程 数据结构 1.你可能会常常发现,写了一段代码后,编译程序时是一大堆的出错 (原因:语法不熟)  ──别担心,这是每个程序员必须经历的事,这时候你就需要更大的耐心及细心,对每一行代码进行仔细人阅读并改正,这个很重要,这可以培养你的理解代码能力,所以要常读程序,不要等到程序运行以后才知道你的程序的结果。  ──如何避免:在写代码以前,要认真的学习计算机语

高精度计算(代码加解析,洛谷p1601,p1303)除法待更新

目录 高精度加法 高精度减法 高精度乘法 高精度加法 我们知道在c++语言中任何数据类型都有一定的表示范围。当两个被加数很大时,正常加法不能得到精确解。在小学,我们做加法都采用竖式方法。那么我们也只需要按照加法进位的方式就能得到最终解。 8 5 6+ 2 5 5-------1 1 1 1 加法进位: c[i] = a[i] + b[i];if(c[i] >=

Java开发实例大全提高篇——Applet的应用

开发十年,就只剩下这套架构体系了! >>>    第21章  Applet的应用 21.1  Applet在html中的使用 实例549  在html中显示Applet HtmlShowApplet.java     public void paint(Graphics g){         g.drawString("html文件已经运行", 50, 50);// 绘制文本

Java开发实例大全提高篇——Java安全

开发十年,就只剩下这套架构体系了! >>>    第6篇  Java安全与Applet应用篇 第20章  Java安全 20.1  Java对称加密 实例531  使用BASE64加密     public static String encryptBASE64(byte[] data) {         //加密数据         return (new BASE64Encoder()

洛谷 凸多边形划分

T282062 凸多边形的划分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 先整一个半成品,高精度过两天复习一下补上 #include <iostream>#include <algorithm>#include <set>#include <cstring>#include <string>#include <vector>#include <map>

2024国赛论文拿奖快对照这几点及评阅要点,勿踩雷区!(国赛最后冲刺,提高获奖概率)

↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ 2024“高教社杯”全国大学生数学建模竞赛已过去第三个夜晚,小伙伴们都累了没有,如果感到思维滞涩,别忘了稍作休息,放松一下自己,准备迎接国赛非常重要的收尾阶段——论文。 国赛这几天的努力最后都