[AGC008C] Tetromino Tiling 题解

FFTotoro · 2022-05-11 13:08:23 · 题解

一道很好的思维题，一贯有 AtCoder 的风格。

观察题目，我们可以得到显而易见的两个结论：

• T, S, Z 三种形状是绝对不可以选择的（原因：这三种形状会将整个 2\times 2K 的长方形分成两个奇数块的形状，填到最后便无法填充）；
• O 形方块可以全选，对答案 K 的贡献值就为它的块数。

现在我们再来考虑剩下的三种方块：

很显然，2 个 J、2 个 I 或 2 个 L 可以构成一个 2\times4 的长方形，对 K 的贡献值为 2，我们称其为方案一。但是，还有一种情况——用 1 个 J、1 个 I 和 1 个 L，可以构成一个 2\times6 的长方形，对 K 的贡献值为 3，我们称其为方案二。

易证 2 个及以上的“方案二”构成的长方形可以由“方案一”（或再加上 1 个“方案二”）来构成，所以只用考虑出现 1 个“方案二”即可。

但是要注意，可以构成“方案二”当且仅当 I,J,K 三种方块的数量都不小于 1。所以需要特判。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  long long i,o,t,j,l; cin>>i>>o>>t>>j>>l; // J 和 L 后面的都不用读入了
  cout<<o+max(i&&j&&l?3+(i-1)/2*2+(j-1)/2*2+(l-1)/2*2:0,i/2*2+j/2*2+l/2*2)<<endl; // 如果只用上文所述的方案二，用完方块还有剩余 1 块那么就不能用；方案一也是类似的道理
  return 0;
}