52 lines
1.0 KiB
C++
52 lines
1.0 KiB
C++
#include <bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
vector<vector<int>> dp; // i = altura, j = largura
|
|
|
|
// ex 1x3 == (1+ 1x2 + 1x1)
|
|
int cortedp(int i, int j){
|
|
if(dp[i][j] != -1) return dp[i][j];
|
|
if(i == j) return 0;
|
|
|
|
int answ = __INT32_MAX__;
|
|
for(int l = i-1; l > 0; l--){
|
|
answ = min(answ, 1+cortedp(i-l, j)+cortedp(l,j));
|
|
}
|
|
for(int r = j-1; r > 0; r--){
|
|
answ = min(answ, 1+cortedp(i, j-r)+cortedp(i,r));
|
|
}
|
|
|
|
return dp[i][j] = answ;
|
|
}
|
|
|
|
int main(){
|
|
ios::sync_with_stdio(false);
|
|
|
|
int a,b;
|
|
cin >> a >> b;
|
|
dp.assign(a+1, vector<int>(b+1, -1));
|
|
|
|
//cout << cortedp(a,b) << '\n'; Recursiva (AC)
|
|
|
|
for(int i = 1; i <= a; i++){
|
|
for(int j = 1; j <= b; j++){ // Calculating rectangle ixj
|
|
if(i == j){ // Base case, no actions
|
|
dp[i][j] = 0;
|
|
}else{
|
|
dp[i][j] = __INT32_MAX__;
|
|
// Vertical cuts
|
|
for(int k = i-1; k > 0; k--){
|
|
dp[i][j] = min(dp[i][j], 1+ dp[i-k][j]+dp[k][j]);
|
|
}
|
|
// Horizontal cuts
|
|
for(int k = j-1; k > 0; k--){
|
|
dp[i][j] = min(dp[i][j], 1+ dp[i][j-k]+dp[i][k]);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
cout << dp[a][b] << '\n';
|
|
|
|
return 0;
|
|
} |