【Luogu1541】乌龟棋

Source and Judge

NOIP2010 提高组 T2
Luogu1541
Caioj1542

Problem

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

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

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

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

现在,告诉你棋盘上每个格子的分数和所有的爬行卡片,你能告诉小明,他最多能得到多少分吗?
【Input】
第1行2个正整数N和M,分别表示棋盘格子数和爬行卡片数。
第2行N个非负整数,a1 a2……aN,其中ai表示棋盘第i个格子上的分数。
第3行M个整数,b1 b2……bM,表示M张爬行卡片上的数字。
输入数据保证到达终点时刚好用光M张爬行卡片。
【Output】
1个整数,表示小明最多能得到的分数。
【Limited conditions】
对于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。
【Sample input】
9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1
【Sample output】
73
【Sample explanation】
小明使用爬行卡片顺序为1,1,3,1,2,得到的分数为6+10+14+8+18+17=73。
注意,由于起点是1,所以自动获得第1格的分数6。

Record

30min

Analysis

请先思考后再展开

一眼dp,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
空间:2560000
时间:21760000
枚举的时候按照n、d、c、b的顺序
{% endfold %}
## Code
{% fold 请先思考后再展开 %}
```cpp
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
#include<algorithm>
#ifdef WIN32
#define BIGN "%I64d"
#else
#define BIGN "%lld"
#endif
using namespace std;
typedef long long ll;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
//*******************全局常量*******************
const int INF=0x3f3f3f3f;
const int MAXN=10;
//*******************全局定义*******************
int ct[5];
int s[400];
int f[50][50][50][50];
//*******************实现*******************
//*******************主函数*******************
int main()
{
int n,m;scanf("%d%d",&n,&m);
for(int i=0;i<=n-1;i++) scanf("%d",&s[i]);
for(int i=1;i<=m;i++)
{
int t;
scanf("%d",&t);
ct[t]++;
}
f[0][0][0][0]=s[0];
for(int i=0;i<=n-2;i++)
{
for(int d=0;d<=ct[4];d++)
{
for(int c=0;c<=ct[3];c++)
{
for(int b=0;b<=ct[2];b++)
{
int a=i-4*d-3*c-2*b;
if(a<0) break;
if(a>ct[1]) continue;//debug
f[a+1][b][c][d]=mymax(f[a+1][b][c][d],f[a][b][c][d]+s[i+1]);
f[a][b+1][c][d]=mymax(f[a][b+1][c][d],f[a][b][c][d]+s[i+2]);
f[a][b][c+1][d]=mymax(f[a][b][c+1][d],f[a][b][c][d]+s[i+3]);
f[a][b][c][d+1]=mymax(f[a][b][c][d+1],f[a][b][c][d]+s[i+4]);
}
}
}
}
printf("%d",f[ct[1]][ct[2]][ct[3]][ct[4]]);//n-1
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/e616.html
转载请注明出处,谢谢!