2.6学习总结10

动态规划

知识点

动态规划是一种解决问题的策略，适用于具有重叠子问题和最优子结构性质的问题。

动态规划的基本思想是将原问题分解为一系列子问题，通过求解子问题的最优解来得到原问题的最优解。在求解子问题时，利用已经求解过的子问题的解来避免重复计算。

动态规划的步骤如下：

1. 定义状态：将原问题划分为子问题，并定义子问题的状态。
2. 定义状态转移方程：确定子问题之间的关系，建立状态转移方程。
3. 初始化：确定初始状态的值。
4. 确定计算顺序：根据状态转移方程，确定计算子问题的顺序。
5. 计算最优解：按计算顺序依次计算子问题的最优解。
6. 求解原问题：根据子问题的最优解，求解原问题的最优解。

动态规划适用于求解最优化问题，例如最长公共子序列问题、0-1背包问题等。它可以显著提高计算效率，减少不必要的重复计算。

台阶问题

假设有n个台阶，现在要求上楼梯的方式数目。每次只能走1步或2步，问有多少种不同的方式可以到达第n个台阶？

我们定义一个dp数组，dp[i]表示到达第i个台阶的不同方式数目。

对于第i个台阶，有两种情况：

1. 从第i-1个台阶走1步到达第i个台阶；
2. 从第i-2个台阶走2步到达第i个台阶。

所以可以得到状态转移方程：dp[i] = dp[i-1] + dp[i-2]。

初始条件是：dp[1] = 1，dp[2] = 2。

根据状态转移方程，可以从第3个台阶开始，依次计算dp数组的值，直到计算到第n个台阶的值。

最终，dp[n]就是到达第n个台阶的不同方式数目。

#include <stdio.h>

// 计算n个台阶有多少种上法
int countWays(int n)
{
    // 创建一个长度为n的数组，用来保存计算结果
    int dp[n+1];

    // 基础情况
    dp[1]=1;
    dp[2]=2;

    // 遍历计算每个台阶的上法
    for (int i=3;i<=n;i++)
        dp[i]=dp[i-1]+dp[i-2];

    // 返回最后一个台阶的上法数量
    return dp[n];
}

int main()
{
    int n;
    printf("请输入台阶的数量：");
    scanf("%d", &n);
    printf("共有%d种上法\n", countWays(n));
    return 0;
}
 

P1387 最大正方形

题目描述

在一个 n×m 的只包含 0 和 1 的矩阵里找出一个不包含 0 的最大正方形，输出边长。

输入格式

输入文件第一行为两个整数 n,m(1≤n,m≤100)，接下来 n 行，每行 m 个数字，用空格隔开，0 或 1。

输出格式

一个整数，最大正方形的边长。

输入输出样例

输入 #1复制

4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1

输出 #1复制

2

我们定义一个dp数组,dp[i][j]表示以节点 i , j 为右下角，可构成的最大正方形的边长。

只有a[i][j]==1时，节点i,j才能作为正方形的右下角；

对于一个已经确定的dp[i][j]=x，它表明包括节点i，j在内向上x个节点，向左x个节点扫过的正方形中所有a值都为1；

状转转移方程：if (a[i][j]==1) dp[i][j]=min(min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1])+1;

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,m,b=0,a[101][101],dp[101][101]={0};
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=m;j++)
	    {
	        scanf("%d",&a[i][j]);
	        if(a[i][j]==1)
	            dp[i][j]=min(min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1])+1;
	        b=max(b,dp[i][j]);
	    }
	printf("%d",b);
}

 P1934 封印

题目背景

很久以前，魔界大旱，水井全部干涸，温度也越来越高。为了拯救居民，夜叉族国王龙溟希望能打破神魔之井，进入人界“窃取”水灵珠，以修复大地水脉。可是六界之间皆有封印，神魔之井的封印由蜀山控制，并施有封印。龙溟作为魔界王族，习有穿行之术，可任意穿行至任何留有空隙的位置。然而封印不留有任何空隙！ 龙溟无奈之下只能强行破除封印。破除封印必然消耗一定的元气。为了寻找水灵珠，龙溟必须减少体力消耗。他可以在破除封印的同时使用越行术。

题目描述

神魔之井的封印共有 n 层，每层封印都有一个坚固值。身为魔族的龙溟单独打破一层封印时需要消耗的元气为该层封印的坚固值和封印总层数 n 的平方的乘积； 但他也可以打破第 i 层到第 j 层之间的所有封印( i<j)，总元气消耗为第 i,j 层封印的坚固值之和与第 i,j 层之间所有封印层（包括 i,j 层）的坚固值之和的乘积，但为了不惊动蜀山，第 i,j 层封印的坚固值之和不能大于 t （单独打破可以不遵守）。

输入格式

第一行包含两个正整数 n 和 t。
第二行有 n 个正整数，第 i 个数为 ai​，表示第 i 层封印的坚固值。

输出格式

仅一行，包含一个正整数，表示最小消耗元气。

输入输出样例

输入 #1复制

6 10
8 5 7 9 3 5

输出 #1复制

578

说明/提示

样例解释

先单独打破第一层，再用越行术从第二层直接打破到最后一层。 这样消耗元气 8×62+(5+5)×(5+7+9+3+5)=5788×62+(5+5)×(5+7+9+3+5)=578。

数据范围

对于 10%10% 的数据， n≤10；
对于 50%50% 的数据， n≤100；
对于 70%70% 的数据， n≤500；
对于 100%100% 的数据， n≤1000，ai​(1≤i≤n),t≤20000。

由题目分出两部分

1. "单独打破一层封印时需要消耗的元气为该层封印的坚固值和封印总层数 n 的平方的乘积".

2. "打破第 i 层到第 j 层封印(i<j)的总元气消耗为第 i, j 层封印的坚固值之和与第 i, j 层之间所有封印层（包括第 i, j 层）的坚固值之和的乘积。同时，第 i, j 层封印的坚固值之和必须不大于一个固定值 t" 。

 可由两部分分别推出

1.dp[j]=min(dp[j],dp[j-1]+a[j]*n*n);

2.if(a[j]+a[i]<=t) dp[j]=min(dp[j],dp[i-1]+(a[j]+a[i])*(f[j]-f[i-1]));//i是枚举的点

#include<bits/stdc++.h>
using namespace std;
long long a[1010],sum[1010],dp[1010];
int main()
{
    int n,t,i,j;
    scanf("%d %d",&n,&t);
    for(i=1;i<=n;i++)
    {
		scanf("%lld",&a[i]);
		sum[i]=sum[i-1]+a[i];//前缀和
	}
	for(i=1;i<=n;i++)
	{
		long long m=n*n*a[i]+dp[i-1];
		for(j=1;j<i;j++)
		{
			if(a[i]+a[j]<=t)
			m=min(m,(a[i]+a[j])*(sum[i]-sum[j-1])+dp[j-1]);
		}
		dp[i]=m;
	}
	printf("%lld",dp[n]);
}

 P1115 最大子段和

题目描述

给出一个长度为 n 的序列 a，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度 n。

第二行有 n 个整数，第 i 个整数表示序列的第 i 个数字 ai​。

输出格式

输出一行一个整数表示答案。

输入输出样例

输入 #1复制

7
2 -4 3 -1 2 -4 3

输出 #1复制

4

说明/提示

样例 1 解释

选取 [3,5][3,5] 子段 {3,−1,2}{3,−1,2}，其和为 44。

数据规模与约定

• 对于 40%40% 的数据，保证 n≤2×10^3。

• 对于 100%100% 的数据，保证 1≤n≤2×10^5，−10^4≤ai​≤10^4。

暴力解法 

#include<stdio.h>
int main()
{
	int i,n,k=0;
	long long sum;
	int a[200010]={0};
	scanf("%d",&n);
	k=0;
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sum=a[1];
	for(i=1;i<=n;i++)
	{
		if(k>0)
			k+=a[i];
		else
			k=a[i];
		if(k>sum)
			sum=k;
	}
	printf("%lld\n",sum);
}

动态规划

#include<bits/stdc++.h>
using namespace std;
int n,a[200020],dp[200020],i,ans=-2147483647;
// b[i] 表示截止到 i 时，第 i 个数所在的有效序列的元素和。
int main()
{
   scanf("%d",&n);
   for(i=1;i<=n;i++)   
   {
       scanf("%d",&a[i]);
       if(i==1) dp[i]=a[i];
       else dp[i]=max(a[i],dp[i-1]+a[i]);
       ans=max(ans,dp[i]);
   }
   printf("%d",ans);
   return 0;
}