NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2016高中組決賽
 E.艾迪摺紙趣

作者 主題: E.艾迪摺紙趣  (閱讀 764 次)

darry140

  • 初級會員
  • **
  • 文章數: 32
    • 檢視個人資料
E.艾迪摺紙趣
« 於: 六月 18, 2017, 05:42:19 pm »

代碼: [選擇]
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,a,b) for(int i=(a);i<=(b);i++)
#define mkp make_pair
#define pb push_back
#ifdef darry140
#define debug(...) do{\
fprintf(stderr,"%s - %d : (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
_DO(__VA_ARGS__);\
}while(0)
template<typename I> void _DO(I&&x){cerr<<x<<endl;}
template<typename I,typename...T> void _DO(I&&x,T&&...tail){cerr<<x<<", ";_DO(tail...);}
#else
#define debug(...)
#endif
//}}}
const int maxn=1e2+2;
int n,m;
void read()
{
cin>>n>>m;
}
int mem[maxn][maxn];
int dp(int x,int y)
{
if(x<=0||y<=0) return 1e7;
if(x>y) swap(x,y);
if(x==y) return 1;

if(~mem[x][y]) return mem[x][y];
int ans=1e7;
REP1(i,1,x-1) ans=min(ans,dp(i,y)+dp(x-i,y));
REP1(j,1,y-1) ans=min(ans,dp(x,j)+dp(x,y-j));
return mem[x][y]=ans;
}
void build()
{
memset(mem,-1,sizeof(mem));
}
void sol()
{
printf("%d\n",dp(n,m));
}
int main()
{
read();
build();
sol();
return 0;
}
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 231
    • 檢視個人資料
Re: E.艾迪摺紙趣
« 回覆 #1 於: 十一月 10, 2017, 01:56:05 pm »

這題可以用動態規劃來做,
我們用 A[ i][ j] 來表示長寬為 i、 j 的長方形最少可以分割成幾個正方形,
則 A[ i][ 1]=1 (i=1~N)、A[ 1][ j]=1 (j=1~M),
然後可以用兩層迴圈 i=2~N、j=2~M 來求解。

當 i=j 時, A[ i][ j]=1,
否則做出所有的分割方式找最小值,
例如 A[ i][ k]+A[ i][ j-k] (k=1~M-1) 以及 A[ k][ j]+A[ i-k][ j] (k=1~N-1),
時間複雜度為 O(N*M*(N+M)),得解。
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2016高中組決賽
 E.艾迪摺紙趣