关键词：
题目：
给你一个矩阵，其边长均为整数。你想把矩阵切割成总数最少的正方形，其边长也为整数。切割工作由一台切割机器完成，它能沿平行于矩形任一边的方向，从一边开始一直切割到另一边。对得到的矩形再分别进行切割。
输入数据：
输入文件中包含两个正整数，代表矩形的边长，每边长均在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最接近的分数
P1298最接近的分数题目描述给出一个正小数，找出分子(非负)不超过M，分母不超过N(正数)的最简分数或整数，使其最接近给出的小数。“最接近”是指在数轴上该分数距离给出的小数最近，如果这个分数不惟一，输出“T... 查看详情
钢条切割-递归，记忆性递归，dp(代码片段)
钢条切割方法1：递归importjava.util.Scanner;publicclassCuttingpublicstaticintn=10;publicstaticint[]p=1,5,8,16,10,17,17,20,24,30;publicstaticintcut(intx)intres=0;if(x==0)return0; 查看详情
poj1191棋盘切割（压缩dp+记忆化搜索）
一，题意：中文题二。分析：主要利用压缩dp与记忆化搜索思想三，代码：#include<iostream>#include<stdio.h>#include<string.h>#include<stdlib.h>#include<math.h>usingnamespacestd;constintBig=20000000;intMat[10] 查看详情
bailian4122切割回文dp(代码片段)
4122:切割回文总时间限制:1000ms内存限制:65536kB描述阿福最近对回文串产生了非常浓厚的兴趣。如果一个字符串从左往右看和从右往左看完全相同的话，那么就认为这个串是一个回文串。例如，“abcaacba”是一个回文串，... 查看详情
poj8471切割回文dp北大acm/icpc竞赛训练(代码片段)
1#include<iostream>2#include<vector>3#defineINF1000004usingnamespacestd;56strings;7chara[1005];8vector<int>hui[1005];//hui[i]里的k指k到i组成回文9intdp[1005];//dp[i]代表前i个字符要切几刀1011intma 查看详情
uva10003cuttingsticks区间dp
...p;problem=944 题目大意：给你一个长度为L的木条，和N个切割点，每次切割的代价是当前切割木条的长度，问最小代价是多少。 解题思路：很显然的区间DP，dp(i,j) 查看详情
codeforces757dfelicity'sbigsecretrevealed（状压dp）
题意：给定一个01串，一个有效的n切割定义如下：一个横杠代表一次切割，第一条横杠前面的01串不算，最后一条横杠后面的01串不算，将两个横杠中的01串转化成十进制数字，假设这些数字的最大值是MAX且这些数字囊括了1-MAX的... 查看详情
蓝桥杯：矩阵乘法（区间dp）
...[l][r]=min(dp[l][r],dp[l][k]*dp[k][r]+num[l]*num[k]*num[r]).表示用l*k的矩阵去和k*r的矩阵相乘，然后取最小。1 查看详情
[dp]矩阵的最小路径和
题目给定一个矩阵m,从左上角开始每次只能向右或者向下走,最后到达右下角的位置,路径上所有的树子累加起来就是路径和,返回所有的路径中最小的路径和.解法一这是一道经典的动态规划题,状态转移方程为dp[i][j]=min{dp[i-1][j],dp[i]... 查看详情
子矩阵（暴搜（全排列）+dp）
子矩阵（暴搜（全排列）+DP）一、题目子矩阵时间限制: 1Sec 内存限制: 128MB提交: 1 解决: 1[提交][状态][讨论版]题目描述给出如下定义：1.子矩阵：从一个矩阵当中选取某些行和某些列交叉位置所组... 查看详情
poj1191棋盘分割（区间dp，记忆化搜索）
...那一项和我们怎么分的具体方案无关，影响答案的是每个矩阵的矩阵和的平方，由于数据很小，我们可以预处理出每个矩阵的和的平方，执行状态转移。设dp[l1][r1][l2][r2][k]是矩阵l1,r1,l2,r2切割k次的最小值，我们可以枚举是横着切... 查看详情
矩阵快速幂优化dp模板
...s://blog.csdn.net/china_xyc/article/details/89819376#commentBox关于能用矩阵乘法优化的DP题目，有如下几个要求：转移式只有加法，清零，减法etc.，max和min运算不允许转移式中关于前几位dp结果得到的系数必须是常量转移次数一般超级多由于... 查看详情
hihocoder1580dp最大子矩阵和
题意：给出n*m的矩阵求最大子矩阵和，要求必须把矩阵中的某一个元素替换成p代码：//求最大子矩阵和，容易想到压缩之后dp但是这道题要求必须替换一次p，必然优先替换最小的。//这样如果求得的结果恰好等于这个矩阵所有的... 查看详情
获取背包 DP 矩阵中选定项目的列表
】获取背包DP矩阵中选定项目的列表【英文标题】：GettinglistofselecteditemsinKnapsackDPmatrix【发布时间】：2016-10-0107:22:59【问题描述】：我已经尝试实现堆栈溢出AnsweredSolution。但它不起作用。测试用例：intval[]=10,40,30,50;intwt[]=5,4,6,3;W=1... 查看详情
hdu5607graph（矩阵优化+概率dp）
...到j点的概率。可是该题的k高达1e9。所以依照套路。要用矩阵相乘来优化。第一次写矩阵相乘。大概的意思就是利用矩阵实现递推。而且由于每次递推的过程一样，所以就相当于右乘这个矩阵的k次方。用矩阵高速幂就可以。矩阵... 查看详情
codeforcesround#341(div.2)e.wetsharkandblocks（矩阵优化dp）
...[j]*cnt[k]，k是指枚举放1~9中哪一位。因为b特别大，显然要矩阵优化，知道了DP方程，其实矩阵的构造特别简单。 查看详情
（poj3744）scoutyyfi（概率dp+矩阵快速幂）
...为n个数字上限很大，所以常规的概率dp基本不可能，要用矩阵优化。把路程分成n+1段，分别计算通过每段的成功率，即刚好跨越地雷的概率（dp[地雷x+1]）算好每段之后把每段的成功率相乘。（若有两颗地雷相邻那么成功率是0）#... 查看详情
noip2014pj子矩阵[搜索｜dp]
题目描述给出如下定义：子矩阵：从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵（保持行与列的相对顺序）被称为原矩阵的一个子矩阵。例如，下面左图中选取第2、4行和第2、4、5列交叉位置的元素得到一个2*3的... 查看详情