[蓝桥杯][2013年第四届真题]剪格子

如下图所示，3  x  3  的格子中填写了一些整数。 

+--*--+--+ 

|10*  1|52| 

+--****--+ 

|20|30*  1| 

*******--+ 

|  1|  2|  3| 

+--+--+--+  

我们沿着图中的星号线剪开，得到两个部分，每个部分的数字和都是60。 

本题的要求就是请你编程判定：对给定的m  x  n  的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。 

如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。  

如果无法分割，则输出  0。 

输入

程序先读入两个整数  m  n  用空格分割  (m,n< 10)。 

表示表格的宽度和高度。 

接下来是n行，每行m个正整数，用空格分开。每个整数不大于10000。 

输出

输出一个整数，表示在所有解中，包含左上角的分割区可能包含的最小的格子数目。 

样例输入

3  3 10  1  52 20  30  1 1  2  3

样例输出

3 dfs 4个参数，前面两个代表坐标，第三个代表不断变化的总和，最后一个是总和相等的个数，取较小者。

#include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;const int inf=0x3f3f3f;int dir[4][2]={ { 1,0},{-1,0},{ 0,1},{ 0,-1}};int maps[15][15];int vis[15][15];int n,m,all=0,ans=inf;void dfs(int x,int y,int sum,int cnt){ if(sum>all/2) return ; if(sum==all/2) ans=min(ans,cnt); else { for(int i=0;i<4;i++) { int xx=x+dir[i][0]; int yy=y+dir[i][1]; if(xx>=0&&xx
             
              =0&&yy
             
            
           
          
         
        
       

问题描述

　　给定一个n*m的矩阵A，求A中的一个非空子矩阵，使这个子矩阵中的元素和最大。

　　其中，A的子矩阵指在A中行和列均连续的一块。

输入格式

　　输入的第一行包含两个整数n, m，分别表示矩阵A的行数和列数。

　　接下来n行，每行m个整数，表示矩阵A。

输出格式

　　输出一行，包含一个整数，表示A中最大的子矩阵中的元素和。

样例输入

3 3

-1 -4 3

3 4 -1

-5 -2 8

样例输出

10

题目大意：求连续行、列的子矩阵的最大元素和。由于行、列必须是连续的，所以可以先求出每一列前n行的和，然后再枚举一个 行的开始和结束就可以啦，然后再用最大字段和求出最大和。本质是将二维的转化为一维的。

#include 
       
        #include
        
         using namespace std;long long dp[505][505];int main(){    long long n,m,i,j,k;    cin>>n>>m;    for(i=1;i<=n;i++)    {        for(j=1;j<=m;j++)        {            cin>>dp[i][j];            dp[i][j]+=dp[i][j-1];        }    }    long long maxx=dp[1][1];    for(i=1;i<=m;i++)    {        for(j=i;j<=m;j++)        {            long long s=0;            for(k=1;k<=n;k++)            {                s+=dp[k][j]-dp[k][i-1];                if(s>maxx)                    maxx=s;                if(s<0)                    s=0;            }        }    }    cout<
         
          <
         
        
       

一个正整数可以划分为多个正整数的和，比如n=3时： 

3；1＋2；1＋1＋1； 

共有三种划分方法。 

给出一个正整数，问有多少种划分方法。 

数据规模和约定 

n< =100 

输入

一个正整数n 

输出

一个正整数，表示划分方案数 

样例输入

3

样例输出

3 动态规划题

建立一个二维数组横行代表将一个数拆几份

      竖行代表要拆分的数那么方案数=arr[n][k].

      我们要简化状态对于每一种分法我把它分成两种情况

      1.分法里至少有一个1  比如 5 = 1+2+2  5 = 1+1+3

      2.分法里没有1  比如 5 = 3+2 

      所以方案数=没有1的所有分法+有1的所有分法

#include 
         
          #include
          
           using namespace std;int vis[101][101];int f(int m,int i){    if(vis[m][i])        return vis[m][i];    if(m==i||i==1)        return 1;    if(i>m)        return 0;    return vis[m][i]=f(m-1,i-1)+f(m-i,i);}int main(){ int n; cin>>n; long long  sum=0; for(int i=1;i<=n;i++) {     sum+=f(n,i); } cout<
           
            <
           
          
         

题目描述

小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共m盆。通过调查顾客的喜好，小明列出了顾客最喜欢的n种花，从1到n标号。为了在门口展出更多种花，规定第i种花不能超过ai盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。 

试编程计算，一共有多少种不同的摆花方案。 

 

样例说明

有2种摆花的方案，分别是(1，1，1，2)，  (1，1，2，2)。括号里的1和2表示两种花，比如第一个方案是前三个位置摆第一种花，第四个位置摆第二种花。 

数据规模和约定 

对于100%数据，有0< n≤100，0< m≤100，0≤  ai≤100。 

输入

第一行包含两个正整数n和m，中间用一个空格隔开。 

第二行有n个整数，每两个整数之间用一个空格隔开，依次表示a1、a2、……an。 

输出

输出只有一行，一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对1000007取模的结果。

样例输入

2  4 3  2

样例输出

2

#include 
           
            #include
            
             using namespace std;#define mod 1000007int a[505][105],f[105];int main(){  int n,m;  cin>>n>>m;  int i,j;  for(i=1;i<=n;i++)  {      cin>>f[i];  }  a[0][0]=1;  for(i=1;i<=n;i++)  {      for(j=0;j<=m;j++)//摆放的总盆数      {          for(int h=0;h<=min(j,f[i]);h++)//第i种花摆放k盆          {              a[i][j]=(a[i][j]+a[i-1][j-h])%mod;          }      }  }  cout<
             
              <