luogu P1541 乌龟棋题解

ゝ一世哀愁。 2023-06-01 15:54 46阅读 0赞

#  #

luoguP1541 乌龟棋 题解

[题目描述][Link 1]

这道题目想状态的时候想多了一维表示当前走了多少步，其实这个完全没有必要，因为根据你的牌的使用就可以知道你当前在哪一个位置。

#### 状态 ####

设\\(f\[i\]\[j\]\[k\]\[l\]\\)表示已经用了\\(i\\)张步数为\\(1\\)的牌，\\(j\\)张步数为\\(2\\)的牌，\\(k\\)张步数为\\(3\\)的牌，\\(l\\)张步数为\\(4\\)的牌所能取得的最大分数。

#### 转移 ####

因为只有这四种牌，所以只需要枚举到达当前的步数的最后一步用的那张牌，然后对用四种牌的情况取\\(\\max\\)就可以，再判一下边界就可以了。

#include<iostream> #include<cstdio> using namespace std; const int N=350,M=41; int f[M][M][M][M]; int num[5],a[N]; 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;i<=m;i++) { int x; scanf("%d",&x); num[x]++; } f[0][0][0][0]=a[1]; for (int i=0;i<=num[1];i++) for (int j=0;j<=num[2];j++) for (int k=0;k<=num[3];k++) for (int l=0;l<=num[4];l++) { int now=i+2*j+3*k+4*l+1; if (i) f[i][j][k][l]=max(f[i-1][j][k][l]+a[now],f[i][j][k][l]); if (j) f[i][j][k][l]=max(f[i][j-1][k][l]+a[now],f[i][j][k][l]); if (k) f[i][j][k][l]=max(f[i][j][k-1][l]+a[now],f[i][j][k][l]); if (l) f[i][j][k][l]=max(f[i][j][k][l-1]+a[now],f[i][j][k][l]); } printf("%d\n",f[num[1]][num[2]][num[3]][num[4]]); return 0; }

转载于:https://www.cnblogs.com/last-diary/p/11453418.html

[Link 1]: https://www.luogu.org/problem/P1541

发表评论取消回复

表情：

评论列表（有 0 条评论，46人围观）

还没有评论，来说两句吧...

相关阅读

相关【DP】乌龟棋

这状态设计的真的牛逼本来想了个暴力DP，前i个数选了j个卡片，选的是第k个卡片，然后搞个状压记录选了哪几种卡片，因为卡片一共就4种但是它说的不能选是指同一种是可以重复选

「爱情、让人受尽委屈。」/ 2024年03月24日 10:23/ 0 赞/ 121 阅读

相关题解 luogu P1850 【换教室】

题解 luogu P1850 【换教室】时间：2019.8.6 一晚上（约 3.5h 写完）题目描述对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际

Dear 丶/ 2023年10月09日 09:42/ 0 赞/ 135 阅读

相关题解 luogu P5021 【赛道修建】

题解 luogu P5021 【赛道修建】时间：2019.8.9 20:40 时间：2019.8.12 题目描述 C 城将要举办一系列的赛车比赛。在比赛前，需

今天药忘吃喽~/ 2023年10月09日 09:41/ 0 赞/ 137 阅读

相关 luogu P1541 乌龟棋题解

luoguP1541 乌龟棋题解 [题目描述][Link 1] 这道题目想状态的时候想多了一维表示当前走了多少步，其实这个完全没有必要，因为根据你的牌的使用就可以

ゝ一世哀愁。/ 2023年06月01日 15:54/ 0 赞/ 47 阅读

相关 luogu P1311 选择客栈题解

\\(luogu\\) P1311 选择客栈题解 [题目链接][Link 1] 看到这道题目首先很茫然，一看统计方案数，肯定要什么数论或者数学知识吧，然后就打了个暴力

小咪咪/ 2023年06月01日 15:54/ 0 赞/ 113 阅读

相关题解 Luogu P3959 【宝藏】

来一篇不那么慢的状压？？？话说这题根本没有紫题难度吧，数据还那么水我是不会告诉你我被hack了 -------------------- 一看数据规模，n≤12，果

布满荆棘的人生/ 2023年06月01日 12:42/ 0 赞/ 100 阅读

相关 P1541-乌龟棋

1 pragma GCC optimize("Ofast") 2 include <bits/stdc++.h> 3 define maxn 130

Love The Way You Lie/ 2023年06月01日 08:51/ 0 赞/ 104 阅读

相关【基础练习】【背包DP】codevs1068 乌龟棋题解

题目来自2010NOIP提高组题目描述 Description 小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。乌龟棋的棋盘是一行N个格子，每个格子上一个分数

港控/mmm°/ 2022年08月03日 23:59/ 0 赞/ 235 阅读

相关洛谷P1541 乌龟棋

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

偏执的太偏执、/ 2022年05月27日 12:27/ 0 赞/ 202 阅读

相关【题解】Luogu P1083 借教室

用差分数组(b\[i\])存每天教室的使用情况所以当对区间操作时，其实可以转化成对b数组操作： b[s[i]]+=d[i]; b[t[i]+1]-=d[i

亦凉/ 2021年11月17日 15:02/ 0 赞/ 350 阅读