P1070:道路游戏题解

思路

经过长时间琢磨题解之后,我理解了dalao们的想法。这道题使用一维即可,但是O(n^3)的时间复杂度确实惊人。奈何我太菜了,只能理解这一种,那我也就只能来写写n^3的题解了。

转移方程:F[i] = max(F[i], F[i-k] + sum – cost[curt],其中i表示当前的时间,k表示目前设置的机器人的步数,sum代表累积起来的金币,curt表示当前机器人的编号。其中当curt = 0时,curt需要被设置成n(环形特征)。答案储存在F[m]。

代码

// P1070.cpp
#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 2020;
int table[maxn][maxn];
int cost[maxn];
int F[maxn];
int n, m, p;

int main()
{
    cin >> n >> m >> p;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> table[i][j];
    for (int i = 1; i <= n; i++)
        cin >> cost[i];
    fill(F, F + maxn, -(1e9));
    F[0] = 0;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
        {
            int curt = j - 1;
            if (curt == 0)
                curt = n;
            int sum = table[curt][i];
            for (int k = 1; k <= p; k++)
            {
                if (i - k < 0)
                    break;
                F[i] = max(F[i], F[i - k] + sum - cost[curt]);
                curt--;
                if (curt == 0)
                    curt = n;
                sum += table[curt][i - k];
            }
        }
    cout << F[m];
    return 0;
}

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注