HDU 5100 Chessboard（BestCoder Round #17）（找规律）

Problem Description：

Consider the problem of tiling an n×n chessboard by polyomino pieces that are k×1 in size; Every one of the k pieces of each polyomino tile must align exactly with one of the chessboard squares. Your task is to figure out the maximum number of chessboard squares tiled.

 

Input：

There are multiple test cases in the input file.
First line contain the number of cases T (T≤10000). 
In the next T lines contain T cases , Each case has two integers n and k. (1≤n,k≤100)

 

Output：

Print the maximum number of chessboard squares tiled.

 

Sample Input：

2

6 3

5 3

 

Sample Output：

36

24

题意：给出n*n的矩阵，用1*k规格的骨牌填充它，问最终最多填充多少格子。

分析：如果n<k，矩阵中无法放骨牌，所以只用考虑n>=k的情况：

首先如果某个覆盖方案中仅剩下一个s*s的正方形区域没有被覆盖到，并且s<=k/2，那么这个方案一定最优（详情见下图）

有趣的是，当 n ≥ k 时，让整个棋盘仅剩一个边长不超过 k / 2 的小正方形区域没有覆盖到，这是一定能做到的。不妨把 n 除以 k 的余数记作 r 。如果 r ≤ k / 2 ，那么我们可以直接用横着的小矩形从左向右填充棋盘，再用竖着的小矩形填充余下的部分，最终会剩下 r × r 的小正方形区域。

如果 r > k / 2 呢？我们可以用和刚才类似的方法填充棋盘，使得棋盘右上角仅剩一个 (r + k) × (r + k) 的正方形区域。然后再用 4r 个小矩形像风车一样填充这个 (r + k) × (r + k) 的区域，使得正中间只剩下一个边长为 k – r 的小正方形区域。由于 k – r < k / 2 ，因而此时的覆盖方案再次达到最优。

#include<stdio.h>
#include<string.h>
#include<queue>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;

const int N=1e3+10;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;

typedef long long LL;

int main ()
{
    int T, n, k, ans, a, r;

    scanf("%d", &T);

    while (T--)
    {
        scanf("%d%d", &n, &k);

        ans = -INF;

        if (k > n) ans = 0;
        else
        {
            r = n % k;
            if (r <= k/2) ans = n*n-r*r;
            else
            {
                a = 4*k*r;
                a = (r+k)*(r+k)-a;

                ans = n*n-a;
            }
        }

        printf("%d
", ans);
    }

    return 0;
}