设计一套企业网站设计报价,开公众号的流程,俄语网站设计,洛阳app开发公司动态规划
知识点
动态规划是一种解决问题的策略#xff0c;适用于具有重叠子问题和最优子结构性质的问题。
动态规划的基本思想是将原问题分解为一系列子问题#xff0c;通过求解子问题的最优解来得到原问题的最优解。在求解子问题时#xff0c;利用已经求解过的子问题的…动态规划
知识点
动态规划是一种解决问题的策略适用于具有重叠子问题和最优子结构性质的问题。
动态规划的基本思想是将原问题分解为一系列子问题通过求解子问题的最优解来得到原问题的最优解。在求解子问题时利用已经求解过的子问题的解来避免重复计算。
动态规划的步骤如下
定义状态将原问题划分为子问题并定义子问题的状态。定义状态转移方程确定子问题之间的关系建立状态转移方程。初始化确定初始状态的值。确定计算顺序根据状态转移方程确定计算子问题的顺序。计算最优解按计算顺序依次计算子问题的最优解。求解原问题根据子问题的最优解求解原问题的最优解。
动态规划适用于求解最优化问题例如最长公共子序列问题、0-1背包问题等。它可以显著提高计算效率减少不必要的重复计算。
台阶问题
假设有n个台阶现在要求上楼梯的方式数目。每次只能走1步或2步问有多少种不同的方式可以到达第n个台阶
我们定义一个dp数组dp[i]表示到达第i个台阶的不同方式数目。
对于第i个台阶有两种情况
从第i-1个台阶走1步到达第i个台阶从第i-2个台阶走2步到达第i个台阶。
所以可以得到状态转移方程dp[i] dp[i-1] dp[i-2]。
初始条件是dp[1] 1dp[2] 2。
根据状态转移方程可以从第3个台阶开始依次计算dp数组的值直到计算到第n个台阶的值。
最终dp[n]就是到达第n个台阶的不同方式数目。
#include stdio.h// 计算n个台阶有多少种上法
int countWays(int n)
{// 创建一个长度为n的数组用来保存计算结果int dp[n1];// 基础情况dp[1]1;dp[2]2;// 遍历计算每个台阶的上法for (int i3;in;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它表明包括节点ij在内向上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;
#includebits/stdc.h
using namespace std;
int main()
{int n,m,b0,a[101][101],dp[101][101]{0};scanf(%d %d,n,m);for(int i1;in;i)for(int j1;jm;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;bmax(b,dp[i][j]);}printf(%d,b);
} P1934 封印
题目背景
很久以前魔界大旱水井全部干涸温度也越来越高。为了拯救居民夜叉族国王龙溟希望能打破神魔之井进入人界“窃取”水灵珠以修复大地水脉。可是六界之间皆有封印神魔之井的封印由蜀山控制并施有封印。龙溟作为魔界王族习有穿行之术可任意穿行至任何留有空隙的位置。然而封印不留有任何空隙 龙溟无奈之下只能强行破除封印。破除封印必然消耗一定的元气。为了寻找水灵珠龙溟必须减少体力消耗。他可以在破除封印的同时使用越行术。
题目描述
神魔之井的封印共有 n 层每层封印都有一个坚固值。身为魔族的龙溟单独打破一层封印时需要消耗的元气为该层封印的坚固值和封印总层数 n 的平方的乘积 但他也可以打破第 i 层到第 j 层之间的所有封印( ij)总元气消耗为第 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(55)×(57935)5788×62(55)×(57935)578。
数据范围
对于 10%10% 的数据 n≤10 对于 50%50% 的数据 n≤100 对于 70%70% 的数据 n≤500 对于 100%100% 的数据 n≤1000ai(1≤i≤n),t≤20000。
由题目分出两部分
1. 单独打破一层封印时需要消耗的元气为该层封印的坚固值和封印总层数 n 的平方的乘积.
2. 打破第 i 层到第 j 层封印(ij)的总元气消耗为第 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是枚举的点
#includebits/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(i1;in;i){scanf(%lld,a[i]);sum[i]sum[i-1]a[i];//前缀和}for(i1;in;i){long long mn*n*a[i]dp[i-1];for(j1;ji;j){if(a[i]a[j]t)mmin(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。
暴力解法
#includestdio.h
int main()
{int i,n,k0;long long sum;int a[200010]{0};scanf(%d,n);k0;for(i1;in;i)scanf(%d,a[i]);suma[1];for(i1;in;i){if(k0)ka[i];elseka[i];if(ksum)sumk;}printf(%lld\n,sum);
}
动态规划
#includebits/stdc.h
using namespace std;
int n,a[200020],dp[200020],i,ans-2147483647;
// b[i] 表示截止到 i 时第 i 个数所在的有效序列的元素和。
int main()
{scanf(%d,n);for(i1;in;i) {scanf(%d,a[i]);if(i1) dp[i]a[i];else dp[i]max(a[i],dp[i-1]a[i]);ansmax(ans,dp[i]);}printf(%d,ans);return 0;
}
