HNU OJ10086 挤挤更健康记忆化搜索DP

挤挤更健康

Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:65536KB

Total submit users: 339, Accepted users: 216

Problem 10086 : No special judgement

Problem description

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

Input

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

Output

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

Sample Input

Sample Output

4

8

Judge Tips

当N=4时最优的铺砖方法 AABB AABB CCDD CCDD A，B，C，D为四块方砖的代号。其他的铺法，例如： AAAB AAAC AAAD EFGH 需要的8块砖,不是最少的。

题目链接：http://acm.hnu.cn/online/?action=problem&type=show&id=10086

用边长小于N的正方形方砖（注意，不要求所有的方砖大小相同）,
不重叠地铺满N*N的正方形房间，最少要几块方砖。可以将n*n的大正方形分成若干的小矩形，
然后对每一个小矩形递归地求解，但是分块方法应该具有普遍性，而且分块数目应该尽量地少。
最好的情况莫过于将正方形分成两块，对于这道题，我们可以考虑将正方形分成n*k和n*(n-k)的两块小矩形，
每一块都恰好被边长小于n的正方形以最优的方式填满（即数目最小的填充方式）。使用动态规划法，可得递归方程

f(x,y)= 1, x=y,x<n;

f(y,x), x<y;

min(f(k,y)+f(x-k,y)) (x/2<=k<=x-1) x>y或者x=y=n;

然后爆搜肯定超时，因为我试过了，所以记忆化搜索下

/*

User: 96655 , Problem : 10086

Language : GNU C++ , Judge Result: Accepted

*/

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cmath>

using namespace std;

typedef long long LL;

const int INF=0x3f3f3f3f;

int n;

int a[][];

int f(int x,int y)

{

    if(a[x][y]!=-)return a[x][y];

    if(x==y&&x<n)return a[x][y]=;

    if(x<y)return a[x][y]=f(y,x);

    int tt=INF;

    for(int i=x/;i<=x-;++i)

    {

       tt=min(f(i,y)+f(x-i,y),tt);

    }

    return a[x][y]=tt;

}

int main()

{

   int  T;

    scanf("%d",&T);

    while(T--)

    {

        memset(a,-,sizeof(a));

        scanf("%d",&n);

        printf("%d\n",f(n,n));

    }

   return ;

}

CCDD

HNU OJ10086 挤挤更健康 记忆化搜索DP

HNU OJ10086 挤挤更健康记忆化搜索DP