基础简单DP
2024-08-29 05:28:57
状态比较容易表示,转移方程比较好想,问题比较基本常见 递推、背包、LIS(最长递增序列),LCS(最长公共子序列)
HDU 2048 数塔
由上往下推 状态数太多(100!) 可以由下往上推:
dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+dp[i][j])
储存的话就直接一个二维数组a[110][110]
HDU2018 母牛
有一头母牛,它每年年初生一头小母牛。每头小母牛从第四个年头开始,每年年初也生一头小母牛。请编程实现在第n年的时候,共有多少头母牛?
斐波那契数列 递推 线性递归
dp[i]=dp[i-1]+dp[i-3];
HDU2044 一只小蜜蜂
斐波那契数列 递推 线性递归
先发现 n(n>=3)可由n-1及n-2到达 所以递推得到到达n的方法是到达n-1的方法+到达n-2的方法
HDU2050 折线分割平面
①n条直线能把平面分成几部分: 2+2+3+4......递推公式 f(n)=f(n-1)+n
②一个圆与n条直线 这些直线中每一条在圆内同其他直线相交,假设没有3条直线相交于一点,试问这些直线将圆分成多少区域:
与①相同
现在看下本题 平面的部分数与顶点即直线的交点有关 n=1时有2条线1个交点 部分为2 n=2时有3有4条线6个交点部分为7 所以n=n-1时有 2*(n-1)条线所以n=n时可增加2*2*(n-1)+1(本身的顶点)个部分
即递推公式为 f(n)=f(n-1)+4*(n-1)+1;
codeforces 429B B. Working out
先处理出从左上到右下的最大值和左下到右上的最大值然后枚举交点和进出的方向
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int dp1[][],dp2[][],dp3[][],dp4[][];
int ans[][];
//(1,1)->(i,j)+(i,j)->(n,m)+(n,1)->(i,j)+(i,j)->(1,m);
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
scanf("%d",&ans[i][j]);
}
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
dp1[i][j]=max(dp1[i-][j],dp1[i][j-])+ans[i][j];
}
}
for(int i=n;i>=;i--){
for(int j=m;j>=;j--){
dp2[i][j]=max(dp2[i+][j],dp2[i][j+])+ans[i][j];
}
}
for(int i=;i<=n;i++){
for(int j=m;j>=;j--){
dp3[i][j]=max(dp3[i-][j],dp3[i][j+])+ans[i][j];
}
}
for(int i=n;i>=;i--){
for(int j=;j<=m;j++){
dp4[i][j]=max(dp4[i][j-],dp4[i+][j])+ans[i][j];
}
}
int cnt=;
for(int i=;i<n;i++){
for(int j=;j<m;j++){
cnt=max(cnt,dp1[i-][j]+dp2[i+][j]+dp3[i][j+]+dp4[i][j-]);
cnt=max(cnt,dp1[i][j-]+dp2[i][j+]+dp3[i-][j]+dp4[i+][j]);
}
}
printf("%d\n",cnt);
return ;
}
最新文章
- 动态生成二维码插件 jquery.qrcode.js
- Python-函数的返回值
- Linux 笔记
- c++错误——intermediate.manifest : general error c1010070很傻的错
- B. Shaass and Bookshelf DP
- win2008 r2 远程桌面问题
- 实现自己的脚本语言ngscript之三:语法设计
- zoj 1372
- Objective-C实现变参函数
- NSDateComponents
- 23个适合Java开发者的大数据工具和框架
- Spring AOP小记
- 管理和安装 chart - 每天5分钟玩转 Docker 容器技术(168)
- Odoo 12 开发手册指南(八)—— 业务逻辑 – 业务流程的支持
- 利用OpenCV给图像添加中文标注
- mysqldump 和mysqlbinlog
- 了解AutoCAD对象层次结构 —— 3 ——数据库
- Python学习(二十二)—— 前端基础之BOM和DOM
- thinkphp 3.1.3 配置debug开启报错
- Oarcle 入门之like关键字
热门文章
- mysql 基础练习题(一)
- ip地址查询python3小工具_V0.0.1
- Design Log Storage System
- [转帖]英特尔首款采用10nm技术的混合CPU“Lakefield”即将发布
- 【0.4】mysql版本特性(5.6-8.0)【转】
- GCD和LCM
- php 正则替换特殊字符 和检测是否是中文
- dos2unix、diff命令
- 一篇文章理解JS继承——原型链/构造函数/组合/原型式/寄生式/寄生组合/Class extends
- 交替方向乘子法(ADMM)的原理和流程的白话总结