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;
}

惨绝人寰啊 QvQ

分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

0 条评论

发表评论

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