http://vn.spoj.com/problems/VNCUT/

Người ta dùng máy cắt để cắt một hình chữ nhật có kích thước MxN (N, M nguyên dương ≤ 5000) thành một số ít nhất các hình vuông có kích thước nguyên dương và có các cạnh song song với cạnh hình chữ nhật ban đầu. Máy cắt khi cắt luôn cắt theo phương song song với một trong hai cạnh của hình chữ nhật và chia hình chữ nhật thành hai phần.

Input

Gồm 2 số là kích thước M,N cách nhau bởi dấu cách.

Output

Ghi số k là số hình vuông được tạo ra

Example

Input:
5 6

Output:
5

Lần làm 1 (16,67đ): Ta có thể nhận thấy sự đệ quy trong bài toán này! Tức là với đầu vào lớn ta hoàn toàn có thể dựa vào bài toán nhỏ đã tính toán trước đó để làm! ==> Bây giờ ta đi tính bài toán cơ bản => Do đây là hình chữ nhật nên vai trò của 2 canh ngang nhau ta chỉ cần tính F(a,b) với a<b => Gọi F(a,b) là số hình vuông nhỏ nhất cắt được từ hình chữ nhật có cạnh a b. F(a,b) = F(b,a) nếu a > b; = 1 nếu a = b; = Min của F(i,j) Vì mỗi nhát cắt thì phải cắt thẳng và chia hình chữ nhật thành 2 phần nên, F(a,b) luôn bằng F(x1,b) + F(x2,b) với x1+x2 = a; (đoạn này chỉ cho x, và y chạy đến a/2 và b/2 là đủ vì chạy tiếp là nó sẽ bị đối xứng và lặp) hoặc bằng F(a,y1) + F(a,y2) với y1+y2 = b; => Ta thử cài đặt nhanh thuật toán đệ quy với công thức này xem sao! Công thức đệ quy là F(a,b) : = 1 nếu a=b; = F(b,a) nếu a>b; = Min (f) code

#include &lt;iostream&gt;
 
using namespace std;
 
#define REP(i,n) for(int i=0; i&lt;(n); i++)
#define FOR(i,a,b) for(int i=(a); i&lt;=(b); i++)
typedef long long LL;
    int a,b;
int F(int a, int b)
{
    if(a == b)
    return 1;
 
     
    if(a &gt; b)
    return F(b,a);
     
    if(b%a == 0)
        return b/a;
     
    int min = b;
     
    for(int i=1; i&lt;=a/2; i++)
    {
        int kq = F(i,b) + F(a-i,b);
        if(kq &lt; min)
        min = kq;
    }
     
    for(int j=1; j&lt;=b/2; j++)
    {
        int kq = F(a,j) + F(a,b-j);
        if(kq &lt; min)
        min = kq;
    }
    return min;
}
 
int main()
{
    cin&gt;&gt;a&gt;&gt;b;
    cout&lt;&lt;F(a,b)&lt;&lt;endl;
    return 0;
}

Làm lần 2: 66,67 đ

Ý tưởng giống trên, nhưng thay vì sử dụng đệ quy ta sẽ dùng mảng để lưu các giái trị trước đó lại (quy hoạch động).

 

Điều ta quan tâm tiếp theo ở đây là thứ tự tính toán ra sao.
Ví dụ như test trên ta có
F[5,6] = F[5,1] + F[5,5]
= F[5,2] + F[5,4]
= F[5,3] + F[5,3]
= F[1,6] + F[4,6]
= F[2,6] + F[3,6]

=> Như vậy F[a,b] chỉ tính được khi F[a, j<b] và F[i<a,b] đã được tính.
Mặt khác, lúc trên ta chỉ tính cho F[a < b], giờ đây để tiện ta làm việc với mọi TH
=> F[a,b] = F[b,a] cho tiện, và ta làm phía trên đường chéo chính là đủ.
Đặc biệt lưu ý rằng ta chỉ xét nửa trên đường chéo chính và ta luôn coi j là cạnh dài hơn i nên a bắt buộc phải < b

– Nếu ko để a<b thì chỉ được 25đ, nếu để mảng F[100][100] thì được 50đ, nếu để F[1000][1000] thì được 66,67 điểm!

#include &lt;iostream&gt;
  
using namespace std;
  
#define REP(i,n) for(int i=0; i&lt;(n); i++)
#define FOR(i,a,b) for(int i=(a); i&lt;=(b); i++)

typedef long long LL;

int main()
{
	int ax,bx,a,b;
    cin&gt;&gt;ax&gt;&gt;bx;
    //bat buoc
    a = min(ax,bx);
    b = max(ax,bx);
    
   	int F[b+1][b+1];
   	
   	FOR(i,1,a)
   	{
   		FOR(j,i,b)
   		{
   			//Tinh F[i,j]
   			if(i == j)
   			{
   				F[i][j] = F[j][i] = 1;
   			}else{
   				if(j%i == 0)
   				{
   					F[i][j] = F[j][i] = j/i;
   				}else{
   					int Min = j;
   					
   					//Giu j chay i
   					FOR(h,1,i/2)
   					{
   						int kq = F[h][j] + F[i-h][j];
   						if(kq &lt; Min)
   							Min = kq;
   					}
   					
   					FOR(c,1,j/2)
   					{
   						int kq = F[i][c] + F[i][j-c];
   						if(kq &lt; Min)
   							Min = kq;
   					}
   					
   					F[i][j] = F[j][i] = Min;
   				}
   			}
   		}
   	}
   	
   	cout&lt;&lt;F[a][b]&lt;&lt;endl;
    return 0;
}

 

Advertisements