寒假5

[蓝桥杯][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
dfs 4个参数，前面两个代表坐标，第三个代表不断变化的总和，最后一个是总和相等的个数，取较小者。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
#include <queue>
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<n&&yy>=0&&yy<m&&!vis[xx][yy])
           {
               vis[xx][yy]=1;
               dfs(xx,yy,sum+maps[xx][yy],cnt+1);
               vis[xx][yy]=0;
           }
       }
   }
}
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            scanf("%d",&maps[i][j]);
            all+=maps[i][j];
        }
    }
    memset(vis,0,sizeof(vis));
    vis[0][0]=1;
    dfs(0,0,maps[0][0],1);
    if(ans==inf)
    {
        cout<<0<<endl;
    }
    else
    {
        cout<<ans<<endl;
    }
    return 0;
}

问题描述
　　给定一个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 <iostream>
#include<bits/stdc++.h>
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<<maxx<<endl;
    return 0;

}

一个正整数可以划分为多个正整数的和，比如n=3时：
3；1＋2；1＋1＋1；
共有三种划分方法。
给出一个正整数，问有多少种划分方法。

数据规模和约定
n< =100

输入

一个正整数n

输出

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

样例输入

样例输出

3
动态规划题

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

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

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

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

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

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

#include <iostream>
#include<bits/stdc++.h>
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<<sum<<endl;
 return 0;
}

题目描述

小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共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

样例输出

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define mod 1000007
int 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<<a[n][m]<<endl;
  return 0;
}