P1541 乌龟棋【记忆化搜索】

题目背景

小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。

题目描述

乌龟棋的棋盘是一行

乌龟棋中

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

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

现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？

输入格式

每行中两个数之间用一个空格隔开。

第

第 $22行NN个非负整数，a_1,a_2,…,a_Na1,a2,…,aN，其中a_iai表示棋盘第ii个格子上的分数。$

第 $33行MM个整数，b_1,b_2,…,b_Mb1,b2,…,bM，表示M张爬行卡片上的数字。$

输入数据保证到达终点时刚好用光

输出格式

输入输出样例

输入 #1<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>

9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1

输出 #1<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>

思路

　　裸的记忆化搜索，开四维记录一下每张牌的用量然后dfs就可以了

CODE

 1 #include <bits/stdc++.h>
 2 #define dbg(x) cout << #x << "=" << x << endl
 3 #define eps 1e-8
 4 #define pi acos(-1.0)
 5 
 6 using namespace std;
 7 typedef long long LL;
 8 
 9 const int inf = 0x3f3f3f3f;
10 
11 template<class T>inline void read(T &res)
12 {
13     char c;T flag=1;
14     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
15     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
16 }
17 
18 namespace _buff {
19     const size_t BUFF = 1 << 19;
20     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
21     char getc() {
22         if (ib == ie) {
23             ib = ibuf;
24             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
25         }
26         return ib == ie ? -1 : *ib++;
27     }
28 }
29 
30 int qread() {
31     using namespace _buff;
32     int ret = 0;
33     bool pos = true;
34     char c = getc();
35     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
36         assert(~c);
37     }
38     if (c == '-') {
39         pos = false;
40         c = getc();
41     }
42     for (; c >= '0' && c <= '9'; c = getc()) {
43         ret = (ret << 3) + (ret << 1) + (c ^ 48);
44     }
45     return pos ? ret : -ret;
46 }
47 
48 const int maxn = 1e5 + 7;
49 
50 int n, m;
51 
52 int a[maxn];
53 int b[maxn];
54 
55 int f[50][50][50][50];
56 
57 map<int, int> mp;
58 
59 int dfs(int n1, int n2, int n3, int n4) {
60     if(f[n1][n2][n3][n4]) {
61         return f[n1][n2][n3][n4];
62     }
63     if(n1 == mp[1] && n2 == mp[2] && n3 == mp[3] && n4 == mp[4]) {
64         return 0;
65     }
66     int pos = n1 + n2 * 2 + n3 * 3 + n4 * 4 + 1;
67     int ans = 0;
68     if(n1 < mp[1]) {
69         ans = max(ans, dfs(n1 + 1, n2, n3, n4) + a[pos + 1]);
70     }
71     if(n2 < mp[2]) {
72         ans = max(ans, dfs(n1, n2 + 1, n3, n4) + a[pos + 2]);
73     }
74     if(n3 < mp[3]) {
75         ans = max(ans, dfs(n1, n2, n3 + 1, n4) + a[pos + 3]);
76     }
77     if(n4 < mp[4]) {
78         ans = max(ans, dfs(n1, n2, n3, n4 + 1) + a[pos + 4]);
79     }
80     return f[n1][n2][n3][n4] = ans;
81 }
82 
83 int main()
84 {
85     read(n);
86     read(m);
87     for ( int i = 1; i <= n; ++i ) {
88         read(a[i]);
89     }
90     for ( int i = 1; i <= m; ++i ) {
91         read(b[i]);
92         mp[b[i]]++;
93     }
94     int ans = dfs(0, 0, 0, 0);
95     printf("%d\n",ans + a[1]);
96     return 0;
97 }

View Code