6月11日 AtCoder Beginner Contest 099
题目链接:https://abc099.contest.atcoder.jp/

A – ABD & B – Stone Monument

过水,不多说

C – Strange Bank

思路:
一开始分析了下复杂度,以为迭代加深DFS可做。结果大样例跑了一万年QWQ。。

后面就想到了背包,完全背包直接从前向后扫一遍,就OK了。

代码:

#include <bits/stdc++.h>
#define LL long long
#define MAXN 100005
#define INF 0x3f3f3f3f
using namespace std;

int n, ans, f[MAXN];
bool flag;
int n6[100], n9[100];


int main()
{
    memset(f, 0x3f, sizeof(f));
    scanf("%d", &n);
    for(int i=0; i<=7; i++) n6[i]=n9[i]=1;
    for(int i=0; i<=7; i++)
    {
        for(int j=1; j<=i; j++) n6[i]*=6;
        for(int j=1; j<=i; j++) n9[i]*=9;
    }
    f[0]=0;
    for(int i=0; i<=n; i++)
    {
        for(int j=0; j<=7; j++)
        {
            if(i+n6[j]<=n) f[i+n6[j]]=min(f[i+n6[j]], f[i]+1);
            if(i+n9[j]<=n) f[i+n9[j]]=min(f[i+n9[j]], f[i]+1);
        }
    }
    printf("%d\n", f[n]);
}

D – Good Grid

思路:
开始想到暴力$n^2*c^3$,后面发现可以通过预处理将复杂度降为$n^2*c+c^3$,然后就可以过了。

代码:

#include <bits/stdc++.h>
#define LL long long
#define MAXN 300005
#define INF 2147483647
using namespace std;

int n, k, ans=INF, num[35][5];
int mp[505][505], c[35][35];

int main()
{
    scanf("%d%d", &n, &k);
    for(int i=1; i<=k; i++) for(int j=1; j<=k; j++) scanf("%d", &c[i][j]);
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) scanf("%d", &mp[i][j]);
    for(int x=1; x<=k; x++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++) num[x][(i+j)%3]+=c[mp[i][j]][x];
        }
    }
    for(int i=1; i<=k; i++)
    {
        for(int j=1; j<=k; j++)
        {
            for(int l=1; l<=k; l++)
            {
                if(i!=j && j!=l && l!=i) ans=min(ans, num[i][0]+num[j][1]+num[l][2]);
            }
        }
    }
    printf("%d\n", ans);
} 

发表评论

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