题解 | #乌龟棋#
乌龟棋
https://ac.nowcoder.com/acm/problem/16590
本题不可以采用dfs爆搜,极其容易TLE,因为时间复杂度大致为:,而M的大小为120,即使在运算过程中达不到,但是也远远大于,所以我们应该使用动态规划。题目中说只有四种牌,这个是可以利用的条件。我们dp的状态表示每张牌已经使用了多少张,我们根据使用的牌数算出向前移动了多少格,再将上一个状态加入,便可算出最大答案。
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using ull = unsigned long long int;
using pll = pair<ll, ll>;
const ll mod = 1e9 + 7;
const int N = 3e7 + 250;
int n, m;
int a[1000], dp[50][50][50][50];
int mp[10];
void dilingtian()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= m; i++)
{
int x;
cin >> x;
mp[x]++;
}
dp[0][0][0][0] = a[1];
for (int i = 0; i <= mp[1]; i++)
for (int j = 0; j <= mp[2]; j++)
for (int k = 0; k <= mp[3]; k++)
for (int l = 0; l <= mp[4]; l++)
{
//val表示此时所在的位置
int val = a[i + 2 * j + 3 * k + 4 * l + 1];
//转移状态
if (i)
dp[i][j][k][l] = max(dp[i][j][k][l], dp[i - 1][j][k][l] + val);
if (j)
dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j - 1][k][l] + val);
if (k)
dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k - 1][l] + val);
if (l)
dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k][l - 1] + val);
}
cout << dp[mp[1]][mp[2]][mp[3]][mp[4]] << endl;
}
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
// cin >> t;
t = 1;
while (t--)
dilingtian();
return 0;
}