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

发表评论

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

你是机器人吗? =。= *