马拦过河卒
这一到题目也是比较基础的动态规划，也可以理解为是递推，主要是运用加法原理，思维难度不大。我们要求从\(（0，0）\)到\(（n，n）\)的方案总数，如果没有马的话，我们可以这么做： 设\(f[i][j]\)为从\(（0，0）\)走到\(（i，j）\)的方案总数，我们知道一定是有上面和左边走来，所以只需要累加上面和左边的方案数即可。我们得出：\[f[i][j]=f[i-1][j]+f[i][j-1]（f[0][0...m]=f[0...n][0]=1)\] 我们来思考一下马的问题： 1.当马拦住了\(（0，0...m）\)或\(（0...n,0)\)的时候，拦住的且后面的必然走不到，所以停止赋值 2.如果马拦住了\(（x，y）\)\(（x≠0，y≠0）\)，则不进行状态转移即可 代码如下：#includeusing namespace std;int main(){ int B1,B2,H1,H2; cin>>B1>>B2>>H1>>H2; int Vis[20][20]={}; int dx[9]={0,2,1,-1,-2,-2,-1,1,2}; int dy[9]={0,1,2,2,1,-1,-2,-2,-1}; for (int i=1;i<=9;i++) { int H3=H1+dx[i]; int H4=H2+dy[i]; if (H3>=0&&H4>=0) Vis[H3][H4]=1; } int Find[20][20]={}; for (int i=0;i<=B2;i++) if (Vis[0][i]==0) Find[0][i]=1; else { for (int j=i;j<=B2;j++) Vis[0][j]==1; break; } for (int i=0;i<=B1;i++) if (Vis[i][0]==0) Find[i][0]=1; else { for (int j=i;j<=B1;j++) Vis[j][0]=1; break; } for (int X=1;X<=B1;X++) for (int Y=1;Y<=B2;Y++) if (Vis[X][Y]==0) Find[X][Y]=Find[X-1][Y]+Find[X][Y-1]; cout<
农田个数
题目描述
你的老家在农村。过年时，你回老家去拜年。你家有一片N×MN×M农田，将其看成一个N×MN×M的方格矩阵，有些方格是一片水域。你的农村伯伯听说你是学计算机的，给你出了一道题： 他问你：这片农田总共包含了多少个不存在水域的正方形农田。
两个正方形农田不同必须至少包含下面的两个条件中的一条： 1 边长不相等 2 左上角的方格不是同一方格输入格式
输入数据第一行为两个由空格分开的正整数N、M（1<=m< n <=1000）
第2行到第N+1行每行有M个数字（0或1），描述了这一片农田。0表示这个方格为水域，否则为农田（注意：数字之间没有空格，而且每行不会出现空格）输出格式
满足条件的正方形农田个数。
样例数据
input
3 3
110 110 000output
5
样例解释 边长为1的正方形农田有4块 边长为2的正方形农田有1块 合起来就是5块数据规模与约定
时间限制：1s
空间限制：256MB求多少个正方形，我们设\(F[i][j]\)为以\(（i，j）\)为右下角的正方形个数。如果你画过图，就能够发现：右下角的个数就是以这个点右下角的最大正方形，因为大正方形包含了无数个小正方形，基于正方形的特殊性，我就不难知道这一个性质。然后我们就去考虑，如何去转移，再通过画图可以发现：这个点所能形成的最大正方形与左边的点，左上角的点和上面的点所能形成的最大正方形的个数的最小值有关，也就是\(min(F[i-1][j],F[i][j-1],F[i-1][j-1])\)。那么这个数值具体是多少呢？就是这个数值\(+1\)；即在原来形成的正方形的基础上加上了这个右下角。因此，我们可以得到：\[F[i][j]=min(F[i-1][j],F[i][j-1],F[i-1][j-1])+1\]
代码如下：#includeusing namespace std;int n,m,ans=0;int F[5000][5000];char a[5000][5000];inline int Min(int a,int b,int c){ return min(min(a,b),c);}int main(){ freopen("count.in","r",stdin); freopen("count.out","w",stdout); cin>>n>>m; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) cin>>a[i][j]; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (a[i][j]=='1') F[i][j]=Min(F[i-1][j],F[i][j-1],F[i-1][j-1])+1; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) ans+=F[i][j]; cout< <
矩阵切割
题目描述
给你一个矩阵，其边长均为整数。你想把矩阵切割成总数最少的正方形，其边长也为整数。切割工作由一台切割机器完成，它能沿平行于矩形任一边的方向，从一边开始一直切割到另一边。对得到的矩形再分别进行切割。 输入格式 输入文件中包含两个正整数，代表矩形的边长，每边长均在1—100之间。 输出格式 输出文件包含一行，显示出你的程序得到的最理想的正方形数目。 样例数据 input 5 6 output 5求什么设什么，设\(F[i][j]\)为\((i,j)\)所能组成的最少正方形，那么必然可以得到初值：\(F[i][i]=1(i=min(n,m)).\)同样，我们应该如何去得到呢，\(1...i,1...j\)的矩形其实就是若干个小的矩形矩形得到，因此我们只需要在若干个小矩形和中求最小值即可。即：
\[ f[i][j]=max \begin{cases} F[i][k]+F[i][j-k], k=1...m/2 \\ F[k][j]+F[i-j][j], k=1...n/2\\ \end{cases} \] 因为对称所以k只需要枚举到\(n(m)/2\)#includeusing namespace std;int F[120][120];inline int min(int a,int b){return a>b?b:a;}inline int read(int &k){ int w=1,s=0;char ch=getchar(); for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') w=-1; for (;ch>='0'&&ch<='9';ch=getchar()) s=s*10+ch-'0';k=s*w;}inline void readln(int &x,int &y) {read(x);read(y);}void print(int x){ if (x<0) {putchar('-');x=-x;} if (x>=10) print(x/10); putchar(x%10+'0');}int main(){ freopen("cuts.in","r",stdin); freopen("cuts.out","w",stdout); memset(F,100,sizeof(F)); int n,m;readln(n,m); for (register int i=1;i<=min(n,m);++i) F[i][i]=1; for (register int i=1;i<=n;++i) for (register int j=1;j<=m;++j) { for (register int k=1;k<=i/2;k++) F[i][j]=min(F[i][j],F[k][j]+F[i-k][j]); for (register int k=1;k<=j/2;k++) F[i][j]=min(F[i][j],F[i][k]+F[i][j-k]); } print(F[n][m]);putchar('\n'); fclose(stdin);fclose(stdout); return 0;}
创意吃鱼
思路：同样我们设\(F[i][j]\)为\(i,j\)为右下叫的最大吃鱼方阵。类比一下农田个数，这一个方阵的最大值其实就和左边连续\(0\)的个数和上面连续\(0\)的个数和左上角的最大方阵；因为根据规则，左边和上面必须是\(0\)，因此就与\(0\)的个数有关；又要除了这一串\(0\)之外，还和左上角的有关有关，这一点又和左上角的方阵有关。我们再做一个前缀和，则\(Left[i][j]\)表示\(（i，j）\)为右下脚且不包括本身的连续0个数，Up意义同上。这里不做过多论述：\[F[i][j]=min(Left[i][j],Up[i][j],F[i-1][j-1)+1\]至于另一个方向，按照同样的方法做一遍即可。 代码如下：#includeusing namespace std;int ans=0;int F[3000][3000];int G[3000][3000];int Up[3000][3000];int Map[3000][3000];int Left[3000][3000];int Right[3000][3000];inline int min(int a,int b){return a>b?b:a;}inline int max(int a,int b){return a>b?a:b;}inline int Min(int a,int b,int c){return min(a,min(b,c));}inline int Max(int a,int b,int c){return max(a,max(b,c));}inline int read(int &k){ int w=1,s=0;char ch=getchar(); for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') w=-1; for (;ch>='0'&&ch<='9';ch=getchar()) s=s*10+ch-'0';k=s*w;}inline void readln(int &x,int &y) {read(x);read(y);}void print(int x){ if (x<0) {putchar('-');x=-x;} if (x>=10) print(x/10); putchar(x%10+'0');}int main(){ freopen("meal.in","r",stdin); freopen("meal.out","w",stdout); int n,m;readln(n,m); for (register int i=1;i<=n;++i) for (register int j=1;j<=m;++j) read(Map[i][j]); for (register int i=1;i<=n;++i) for (register int j=2;j<=m;++j) if (!Map[i][j-1]) Left[i][j]=Left[i][j-1]+1; for (register int j=1;j<=m;++j) for (register int i=2;i<=n;++i) if (!Map[i-1][j]) Up[i][j]=Up[i-1][j]+1; for (register int i=1;i<=n;++i) for (register int j=m-1;j;--j) if (!Map[i][j+1]) Right[i][j]=Right[i][j+1]+1; //cout<