NC16590 乌龟棋
乌龟棋
https://ac.nowcoder.com/acm/problem/16590
乌龟棋
题目地址:
基本思路：
比较明显的记忆化搜索，和前两天的一题比较像。
我们使用记忆化搜索令表示位于
的位置使用了
个一步的卡片,
个两步的卡片,
个三步的卡片，
个四步的卡片,
那么我们只要卡片足够就能通过使用相应卡片往,
,
,
这些位置转移,
那么如果我们不使用记忆化，这样搜索的复杂度理论上是的指数级别，肯定会
,
因此我们使用记录使用了
个一步的卡片,
个两步的卡片,
个三步的卡片，
个四步的卡片的结果,
那么由于每种卡片数目不超过,因此此时的复杂度最高为
,很明显能够通过。
同时如果我们直接也是可以的,我们有如下转移方程:
int pos = 1 + c1 + 2 * c2 + 3 * c3 + 4 * c4; if (c1 - 1 >= 0) dp[c1][c2][c3][c4] = max(dp[c1][c2][c3][c4], dp[c1 - 1][c2][c3][c4] + a[pos - 1]); if (c2 - 1 >= 0) dp[c1][c2][c3][c4] = max(dp[c1][c2][c3][c4], dp[c1][c2 - 1][c3][c4] + a[pos - 2]); if (c3 - 1 >= 0) dp[c1][c2][c3][c4] = max(dp[c1][c2][c3][c4], dp[c1][c2][c3 - 1][c4] + a[pos - 3]); if (c4 - 1 >= 0) dp[c1][c2][c3][c4] = max(dp[c1][c2][c3][c4], dp[c1][c2][c3][c4 - 1] + a[pos - 4]);
如果使用，要注意加上最后一个位置。
参考代码：
记忆化搜索：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define ll long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18
inline int read() {
int x = 0, neg = 1; char op = getchar();
while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
return neg * x;
}
inline void print(int x) {
if (x < 0) { putchar('-'); x = -x; }
if (x >= 10) print(x / 10);
putchar(x % 10 + '0');
}
const int maxn = 550;
int n,m,x,a[maxn],b[5];
int dp[50][50][50][50]; // 每种卡片数量不超过40;
int dfs(int pos,int c1,int c2,int c3,int c4) {
if (pos == n) return a[pos]; // 终止条件,卡片用完且到头了;
if (dp[c1][c2][c3][c4] != 0) return dp[c1][c2][c3][c4]; // 记忆化过程;
int ans = 0;
if (c1 + 1 <= b[1]) ans = max(ans, dfs(pos + 1, c1 + 1, c2, c3, c4));
if (c2 + 1 <= b[2]) ans = max(ans, dfs(pos + 2, c1, c2 + 1, c3, c4));
if (c3 + 1 <= b[3]) ans = max(ans, dfs(pos + 3, c1, c2, c3 + 1, c4));
if (c4 + 1 <= b[4]) ans = max(ans, dfs(pos + 4, c1, c2, c3, c4 + 1));
return dp[c1][c2][c3][c4] = ans + a[pos];
}
signed main() {
IO;
cin >> n >> m;
rep(i, 1, n) cin >> a[i];
rep(i, 1, m) cin >> x, b[x]++;
int ans = dfs(1,0,0,0,0);
cout << ans << '\n';
return 0;
}dp:
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define ll long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18
inline int read() {
int x = 0, neg = 1; char op = getchar();
while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
return neg * x;
}
inline void print(int x) {
if (x < 0) { putchar('-'); x = -x; }
if (x >= 10) print(x / 10);
putchar(x % 10 + '0');
}
const int maxn = 550;
int n,m,x,a[maxn],b[5];
int dp[50][50][50][50];
signed main() {
IO;
cin >> n >> m;
rep(i, 1, n) cin >> a[i];
rep(i, 1, m) cin >> x, b[x]++;
for (int c1 = 0; c1 <= b[1]; c1++) {
for (int c2 = 0; c2 <= b[2]; c2++) {
for (int c3 = 0; c3 <= b[3]; c3++) {
for (int c4 = 0; c4 <= b[4]; c4++) {
int pos = 1 + c1 + 2 * c2 + 3 * c3 + 4 * c4; // 初始位置从1开始，要加一;
if (c1 - 1 >= 0) dp[c1][c2][c3][c4] = max(dp[c1][c2][c3][c4], dp[c1 - 1][c2][c3][c4] + a[pos - 1]);
if (c2 - 1 >= 0) dp[c1][c2][c3][c4] = max(dp[c1][c2][c3][c4], dp[c1][c2 - 1][c3][c4] + a[pos - 2]);
if (c3 - 1 >= 0) dp[c1][c2][c3][c4] = max(dp[c1][c2][c3][c4], dp[c1][c2][c3 - 1][c4] + a[pos - 3]);
if (c4 - 1 >= 0) dp[c1][c2][c3][c4] = max(dp[c1][c2][c3][c4], dp[c1][c2][c3][c4 - 1] + a[pos - 4]);
}
}
}
}
int ans = dp[b[1]][b[2]][b[3]][b[4]] + a[n];//最后一个位置要加上;
cout << ans << '\n';
return 0;
}
投递奥克斯等公司7个岗位 >