2236 - 方砖问题

2 
4 
5

4 
8

Hint

当N＝4时 
最优的铺砖方法 

AABB 

AABB 

CCDD 

CCDD 

A，B，C，D为四块方砖的代号。 

其他的铺砖方法，例如： 

AAAB 

AAAC 

AAAD 

EFGH 

需要的8块方砖，不是最少的。 

Solution 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;
    }
}