CF1268B 题解

题目翻译

给你一个杨表，用一个有 \(n\) 个元素的数组 \(a\) 表示杨表每一列的高度。你需要用 \(1 \times 2\) 或 \(2 \times 1\) 的骨牌填充这个杨表，求出最多填充的骨牌数量。

题目分析

我们先来处理一个问题：什么是杨表？

杨表是一种每行长度（或每列高度）单调递减的不规则图，注意这里并非要求严格递减，相邻行的长度（或列的高度）可以相同。

对于这道题，我们将杨表交替染色。为了统一标准，我们规定第奇数行的第奇数个位置染为黑色，交错排列。

例如题目中给出的图片，染色后如下图。

染色之后，我们可以从小的杨表入手，推导关系。如下图所示，我们可以发现，用左上角的两个单位杨图，可以以拼成任意白色和黑色个数相同的杨图，此时填充的骨牌数量即为白色格子数。在该类型图上，我们可以继续拓展，得到所有的杨图，若从一个该类型杨图拓展到目标图需要的格子最少，则可以证明拓展的部分不能再放骨牌（否则会产生新的单位杨图）。

因此，我们得出了结论，可以摆放的骨牌数等于单位杨图数量即黑白块中个数较少的块数。

Codes

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define max_n 300100

void read(int &p)

{

    p = 0;

    int k = 1;

    char c = getchar();

    while (c < '0' || c > '9')

    {

        if (c == '-')

        {

            k = -1;

        }

        c = getchar();

    }

    while (c >= '0' && c <= '9')

    {

        p = p * 10 + c - '0';

        c = getchar();

    }

    p *= k;

    return;

}

void write_(int x)

{

    if(x < 0)

    {

        putchar('-');

        x = -x;

    }

    if(x>9)

    {

        write_(x/10);

    }

    putchar(x%10+'0');

}

void writesp(int x)

{

    write_(x);

    putchar(' ');

}

void writeln(int x)

{

    write_(x);

    putchar('\n');

}

int n,num;

int sum1,sum2;

signed main()

{

    #if _clang_

        freopen("1.in","r",stdin);

        freopen("1.out","w",stdout);

    #endif

    read(n);

    for(int i = 1;i<=n;i++)

    {

        read(num);

        sum1 += num /2;

        sum2 += num/2;

        if(num%2 != 0)

        {

            if(i % 2 !=0)

            {

                sum1++;

            }

            else

            {

                sum2++;

            }

        }

    }

    writeln(min(sum1,sum2));

    return 0;

}

巴特西

CF1268B题解

CF1268B 题解

题目翻译

题目分析

Codes

最新文章

热门文章