首页 > 代码库 > P1298(矩阵切割)DP
P1298(矩阵切割)DP
题目:
给你一个矩阵,其边长均为整数。你想把矩阵切割成总数最少的正方形,其边长也为整数。切割工作由一台切割机器完成,它能沿平行于矩形任一边的方向,从一边开始一直切割到另一边。对得到的矩形再分别进行切割。
输入数据:
输入文件中包含两个正整数,代表矩形的边长,每边长均在1—100之间。
输出数据:
输出文件包含一行,显示出你的程序得到的最理想的正方形数目。
输入输出示例:
CUTS.IN:
5 6
CUTS.OUT:
5
这道题呢可以用DFS+记忆化搜索,因为正在学习DP,所以就用DP写了
所以就用一个数组f[i][j]表示边长为i,j的矩形可以分出最少的正方形
所以就可知if(i==j) f[i][j]=1; 所以就可以知道状态转移方程为:f[i][j]=min{f[i][k1]+f[i][j-k1],f[k2][j]+f[i-k2][j]}
(这里面f[i][k1]+f[i][j-k1]表示将矩形横着切开以后分成的两块包含的最少的矩形,同理可得f[k2][j]+f[i-k2][j]是竖着切开后两块的最少矩形) 1<=k1<j; 1<=k2<i;
代码如下:
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; int f[2100][2100]; int a[2100][2100]; int main() { int n,m; cin>>n>>m; memset(f,10,sizeof(f)); f[0][0]=0; memset(a,0,sizeof(a)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { a[i][j]=1; if(i==j) f[i][j]=1; } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { /*if(i==j) f[i][j]=1;*/ int k1,k2; for(int k=1;k<j;k++)//横着切 { k1=f[i][k]+f[i][j-k]; if(k1<f[i][j]) f[i][j]=k1; } for(int k=1;k<i;k++)//竖着切 { k2=f[k][j]+f[i-k][j]; if(k2<f[i][j]) f[i][j]=k2; } } } /*for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cout<<f[i][j]<<‘ ‘; } cout<<endl; }*/ cout<<f[n][m]<<endl; return 0; }
P1298(矩阵切割)DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。