Jeekr's site
0%

道路游戏 题解

Posted on Edited on

写在前面

这道题在我的题目列表里躺了好久，一直不会做，今天终于做出来了。 思路： \(f_i\)表示i时间的还没有买机器人的最大价值。 由于要计算一系列复杂的东西，这道题的\(O(n^3)\)算法并不适合用填法来做，适合用刷法。 

1
f[i+k] = f[i-1] + \sum^{k}_{kk = 0} {a[i+kk][j + kk]} - c[j]
详细的参考代码，枚举ijk即可。中间求和过程可以预处理，也可以记录下上一次的状态，直接计算。 这道题可以用单调队列把k消掉，不过要转换为填法，这里不再赘述。 ## 代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, p;
int w[N][N];
int f[N];
int c[N];

int main()
{
    cin >> n >> m >> p;
    for (int i = 0; i < n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> w[j][i];
    for (int i = 0; i < n; ++i)
        cin >> c[i];
    memset(f, 0xa0, sizeof f);
    f[0] = 0;
    for (int i = 1; i <= m; ++i)
    // time
    {
        for (int j = 0; j < n; ++j)
        // pos
        {
            int ans = -c[j] + f[i-1];
            for (int k = 0; k < p && i + k <= m; ++k)
            // step
            {
                int t = (j + k) % m;
                ans += w[i + k][t];
                f[i + k] = max(f[i + k], ans);
            }
        }
    }
    cout << f[m] << endl;
}