题解 | #乌龟棋#

乌龟棋

https://ac.nowcoder.com/acm/problem/16590

本题不可以采用dfs爆搜,极其容易TLE,因为时间复杂度大致为:4M4^M,而M的大小为120,即使在运算过程中达不到4M4^M,但是也远远大于10710^7,所以我们应该使用动态规划。题目中说只有四种牌,这个是可以利用的条件。我们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;
}
全部评论

相关推荐

只写bug的程序媛:人家说一本以上,不是及以上
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务