fork download
copy 
  1. //https://c...content-available-to-author-only...s.fi/problemset/task/1744
  2. /*
  3.     dp[i][j] là cách cắt tối thiểu hình chữ nhật ixj thành các hình vuông
  4. */
  5. #include<bits/stdc++.h>
  6. using namespace std;
  7. const long long MaxN = 5e2 + 5, INF= 1e18;
  8. long long a,b, dp[MaxN][MaxN];
  9. int main()
  10. {
  11.     ios_base::sync_with_stdio(0);
  12.     cin.tie(0);
  13.     cin >> a >> b;
  14.     for (long long i=1; i<=a; i++)
  15.     {
  16.         for (long long j=1; j<=b; j++)
  17.         {
  18.             dp[i][j]=INF;
  19.         }
  20.     }
  21.     for (long long i=1; i<=min(a,b); i++)
  22.     {
  23.         dp[i][i]=0;
  24.     }
  25.     for (long long i=1; i<=a; i++)
  26.     {
  27.         for (long long j=1; j<=b; j++)
  28.         {
  29.             if(i!=j)
  30.             {
  31.                 for (long long x = 1; x < i; x++)
  32.                 {
  33.                     dp[i][j] = min(dp[i][j],dp[x][j] + dp[i-x][j] + 1);
  34.                 }
  35.                 for (long long y = 1; y < j; y++)
  36.                 {
  37.                     dp[i][j] = min(dp[i][j],dp[i][y] + dp[i][j-y] + 1);
  38.                 }
  39.             }
  40.         }
  41.     }
  42.     cout << dp[a][b];
  43. }
  44.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/dBHSh7
language:
C++14 (gcc 8.3)
created:
11 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!