思维

CodeForces 349B Color the Fence

Posted on

大家好,我是煞笔。

今天的比赛,开局38分钟写到第一,然后就卡在这题……
真的我觉得我自己挺傻的……事实也是如此,一直卡着之后就去入了另一个弓形矩阵的大坑……还以为要一血来着……

题意:
有 n 块钱,1-9 一共9个数字,每个数字花费确定,要你求出最大的值。

思路
毫无疑问,位数是最重要的。我居然把这个加入了动态的思路上,其实位数应该是从一开始就该确定的。
就是 n / 最小的花费。
剩下的多余的前用来对每一个数进行更换,优先从最左边开始,更换最大的。

AC Code

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(num, ary) memset((ary), (num), sizeof((ary)))

using namespace std;

const int inf = 0x3f3f3f3f;

int ary[15];

int main()
{
    int tot, mn = inf;
    scanf("%d", &tot);
    range(i, 1, 9)
    {
        scanf("%d", ary + i);
        mn = min(mn, ary[i]);
    }
    if (tot < mn) {
        puts("-1");
        return 0;
    }
    int max_digit = tot / mn, l = tot % mn;
    each(i, max_digit)
    {
        bool flag = false;
        rrange(j, 1, 9)
        {
            if (mn + l >= ary[j]) {
                l = mn + l - ary[j];
                putchar(j + '0');
                flag = true;
                break;
            }
        }
        if (!flag)
            putchar(mn + '0');
    }
    return 0;
}
递推

CodeForces 173C Spiral Maximum

Posted on

真是天真了,在计算器上计算复杂度在 1e8 ,给了 3s 时间以为侥幸能过,就用暴力写了……
结果拖到最后也没有写出来……

传送门

题意:
计算最大的有空行的弓形矩阵值。

思路:
如果说你观察仔细的话,你会发现 5×5 方阵 与 3×3 的方阵 差一个格子互补, 7×7 的 方阵 与 5×5 的方阵 差一个格子互补, 9×9 的 方阵 与7× 7 的方阵 差一个格子互补……

那么我们先预处理好每一个 3×3 方阵的值,再通过递推就能知道每一个方阵的值了

AC Code

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(num, ary) memset((ary), (num), sizeof((ary)))

using namespace std;
const int maxn = 550;
const int inf = 0x3f3f3f3f;

int n, m, ans;
int mat[maxn][maxn];
int dp[maxn][maxn][2];
int sum[maxn][maxn];

inline int recSum(int x1, int y1, int x2, int y2)
{
    return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
}

inline void prepSum()
{
    ans = -inf;
    range(i, 1, n)
        range(j, 1, m)
            sum[i][j] = mat[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}

inline int solve(int x, int y, int len)
{
    if (len == 0)
        return dp[x][y][0] = mat[x][y];
    else {
        dp[x][y][0] = recSum(x, y, x + len, y + len);
        dp[x][y][0] -= mat[x + 1][y];
        dp[x][y][0] -= dp[x + 1][y + 1][1];
        return dp[x][y][0];
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    range(i, 1, n)
        range(j, 1, m)
            scanf("%d", &mat[i][j]);
    prepSum();
    range(k, 0, min(n, m))
    {
        rrange(i, 1, n)
            rrange(j, 1, m)
                dp[i][j][1] = dp[i][j][0];
        rrange(i, 1, n)
        {
            if (i + k > n)
                continue;
            rrange(j, 1, m)
            {
                if (j + k > m)
                    continue;
                int p = solve(i, j, k);
                if (k > 0)
                    ans = max(ans, p);
            }
        }
        k++;
    }
    printf("%d\n", ans);
    return 0;
}