Codeforce 1195C 动态规划 状态转移方程
2021/5/18 10:59:14
本文主要是介绍Codeforce 1195C 动态规划 状态转移方程,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
原题链接:http://codeforces.com/problemset/problem/1195/C
题意:给出两行数字(个数相同),每两个数字不能上下或左右相邻,计算出所有数字满足条件的最大和。
思路:利用dp数组存储到达每一个位置的最大值,方法的核心在于选或不选。根据经典的背包问题,选则总价值增加,当前容量减少,不选则保留当前数值不变。回归本题,选则当前值加另一行积累的dp数值,不选则保持本行已积累数值不变。最终两行分别得出所积累的dp数值,选较大的一个输出。总而言之,每一行对应一个数组,记录当前和的最大值。
for(int i=1;i<=n;i++){ dp[0][i]=max(a[i]+dp[1][i-1],dp[0][i-1]); dp[1][i]=max(b[i]+dp[0][i-1],dp[1][i-1]); }
细节:i从1开始,第一次循环用到(i-1)时i即为0,不会有乱七八糟的数据被计算;遍历某一行时,若选择选用本行的数值,相加时引用的是另一行的数据,所以不会发生因遍历而使得数值相邻的情况。
完整代码:
#include <iostream> #include <algorithm> using namespace std; #define N 1000010 typedef long long ll; ll a[N],b[N],dp[3][N]; int main(int argc, char** argv) { int n; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); } for(int i=1;i<=n;i++){ scanf("%lld",&b[i]); } for(int i=1;i<=n;i++){ dp[0][i]=max(a[i]+dp[1][i-1],dp[0][i-1]); dp[1][i]=max(b[i]+dp[0][i-1],dp[1][i-1]); } printf("%lld\n",max(dp[0][n],dp[1][n])); return 0; }
这篇关于Codeforce 1195C 动态规划 状态转移方程的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain