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;
}
标签:杨图,int,题解,void,杨表,骨牌,CF1268B
From: https://www.cnblogs.com/yuhang-ren/p/17110534.html