1. 题目

2. 题解

23333 纯卡常过的。

$1000$ 的数据从 TLE 卡到 AC，关键跑的还挺快的，最慢的点 300+ms（原本 1000ms 都过不了）

具体 $n^3$ 的暴力就是设 $f[i]$ 为用时为 $i$ 的最大收益。

枚举时间、起点、步数即可。

复杂度为 $O(n^3)$

代码长这样（会 T）：

#include <bits/stdc++.h>

#define NS (1005)

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c));
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
}

int n, m, p, coin[NS][NS], cost[NS], f[NS];

int main (int argc, char const* argv[])
{
    IN(n), IN(m), IN(p);
    for (int i = 1; i <= n; i += 1)
        for (int j = 1; j <= m; j += 1)
            IN(coin[i][j]);
    for (int i = 1; i <= n; i += 1) IN(cost[i]);
    for (int i = 1; i <= m; i += 1) f[i] = INT_MIN;
    for (int i = 1, tmp; i <= m; i += 1)
        for (int j = 1; j <= n; j += 1)
        {
            tmp = f[i - 1] - cost[j];
            for (int k = 0, t; k < p && i + k <= m; k += 1)
            {
                t = (j + k - 1) % n + 1;
                tmp += coin[t][i + k];
                f[i + k] = max(f[i + k], tmp);
            }
        }
    printf("%d\n", f[m]);
    return 0;
}

于是我们 T 了 1 个点，而且还有一个点是 900+ms 卡过去的。

仔细观察发现取模那里看的很不爽：

t = (j + k - 1) % n + 1;

取模是很慢的，于是改成：

t = j + k > n ? j + k - n : j + k;

实测这样就能过了 233333

但是最慢的点（就是原本 T 掉了的那个点）还是要 800+ms

于是我们继续优化，怎么优化呢？

在所有的 for 循环变量前面加上 register（寄存器）（就像这样）：

#define REG register
for (REG int i = 1; i <= n; i += 1)

实测最慢 300ms+

我去，，，以后局部变量全开 register 了，太神了。。。

最后再在文件头部加一个 optimize，又快了几 ms

最后代码长这样：

#pragma GCC optimize("Ofast,no-stack-protector")

#include <bits/stdc++.h>

#define REG register
#define NS (1005)

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c));
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
}

int n, m, p, coin[NS][NS], cost[NS], f[NS];

int main (int argc, char const* argv[])
{
    IN(n), IN(m), IN(p);
    for (REG int i = 1; i <= n; i += 1)
        for (REG int j = 1; j <= m; j += 1)
            IN(coin[i][j]);
    for (REG int i = 1; i <= n; i += 1) IN(cost[i]);
    for (REG int i = 1; i <= m; i += 1) f[i] = INT_MIN;
    for (REG int i = 1, tmp; i <= m; i += 1)
        for (REG int j = 1; j <= n; j += 1)
        {
            tmp = f[i - 1] - cost[j];
            for (REG int k = 0, t; k < p && i + k <= m; k += 1)
            {
                t = j + k > n ? j + k - n : j + k;
                tmp += coin[t][i + k];
                f[i + k] = max(f[i + k], tmp);
            }
        }
    printf("%d\n", f[m]);
    return 0;
}

【题解】道路游戏卡常 DP LUOGU – 1070

于2018年2月6日2018年2月6日由XZYQvQ发布

1. 题目

2. 题解

惨绝人寰啊 QvQ

XZYQvQ

0 条评论

发表回复取消回复

【题解】道路游戏 卡常 DP LUOGU – 1070

于2018年2月6日2018年2月6日由XZYQvQ发布

1. 题目

2. 题解

惨绝人寰啊 QvQ

XZYQvQ

0 条评论

发表回复 取消回复

【题解】道路游戏卡常 DP LUOGU – 1070

发表回复取消回复