游客 注册 | 登录
中文 | En

2236 - 方砖问题

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

用边长小于N的正方形方砖（注意，不要求所有的方砖大小相同，请看样例说明）不重叠地铺满N*N的正方形房间，最少要几块方砖。

题目输入

第一行是一个整数T,表示测试数据的组数,接下来的T 行，每一行是一个N(2<=N<=100)

题目输出

对于每一组测试数据输出一行，为最少需要的块数。

输入/输出样例

输入格式

2 
4 
5

输出格式

4 
8

C++解答

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define infinity 0x3f3f3f3f
using namespace std;
int a[104][105];
int slove(int  n)
{
    int i,j,k,t,mins;
    memset(a,0,sizeof(a));
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(i==j&&i!=n)
            {
                a[i][j]=1;
            }
            else
            {
                mins=infinity;
                if(i<j)
                {
                   for(k=j/2;k<=j-1;k++)
                    {
                        mins=min(mins,a[k][i]+a[j-k][i]);
                    }
                }
                else
                {
                    for(k=i/2;k<=i-1;k++)
                    {
                        mins=min(mins,a[k][j]+a[i-k][j]);
                    }
                }
                a[j][i]=a[j][i]=mins;
            }
        }
    }
    return a[n][n];
}
int main()
{
    int t,n;
    cin>>t;
    t--;
    cin>>n;
    cout<<slove(n)<<" "<<endl;
    while(t--)
    {
        cin>>n;
        cout<<slove(n)<<endl;
    }
}
请先登陆