热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

开发笔记:acm选修课——动态规划

篇首语:本文由编程笔记#小编为大家整理,主要介绍了acm选修课——动态规划相关的知识,希望对你有一定的参考价值。

篇首语:本文由编程笔记#小编为大家整理,主要介绍了acm选修课——动态规划相关的知识,希望对你有一定的参考价值。








动态规划


  • 动态规划
    • 动态规划
      • 概念
      • 对比
      • 证明

    • 例题
      • 1.最长上升子序列
      • 2.数塔
      • 3.最长公共子序列
      • 4.字符串的修改
      • 5.海盗分赃
      • 6.The Uxuhul Voting System

    • 附加题:
      • 1.Doing Homework HDU - 1074【状压dp】
      • 2.hdu1024 max sum plus plus





动态规划

动态规划


概念

求最优,
满足最优性原理:
有最优子结构,从小规模最优化到大规模最优化
又名:记忆化搜索


对比

贪心:从小到大
分治:子问题求解独立


证明

求状态转移方程的过程
就是暴力剪枝,记忆化搜索


例题


1.最长上升子序列

http://poj.org/problem?id=2533

找最长上升子序列
优化:可以想到,f[i],第i个上升子序列的最小值,是持续递增的(反证法),以此改成了二分

#include
#include
#include
#ifdef LOCAL
FILE*fp=freopen("text.in","r",stdin);//文件忘记注释害人不浅!!
#endif
int a[1005],f[1005]; //第i个的最小值
signed main(){
int n;
scanf("%d",&n);
for(int i&#61;0;i<n;i&#43;&#43;){
scanf("%d",&a[i]);
}
int cnt&#61;0;
memset(f,0x3f,sizeof(int)*(n&#43;1));
f[0]&#61;-1;//注意边界数据。。
//可以想到&#xff0c;是持续递增的&#xff0c;可以以此二分
for(int i&#61;0;i<n;i&#43;&#43;){
int l&#61;0,r&#61;cnt,m&#61;(l&#43;r)/2;//初始化
while(l<r){
if(f[m]<a[i]&&f[m&#43;1]>&#61;a[i])break;
if(f[m&#43;1]<a[i])l&#61;m&#43;1;
if(f[m]>&#61;a[i])r&#61;m;
m&#61;(l&#43;r)/2;//注意顺序
}
f[m&#43;1]&#61;a[i];
if(m&#61;&#61;cnt)cnt&#43;&#43;;
/*for(int j&#61;cnt;j>&#61;0;j--){
if(f[j]&#61;a[i]){
f[j&#43;1]&#61;a[i];
if(j&#61;&#61;cnt)cnt&#43;&#43;;
}
}*/

}
printf("%d\\n",cnt);
return 0;
}

2.数塔

http://acm.hdu.edu.cn/showproblem.php?pid&#61;2084
自底向上

代码

#include
#include
#include
int a[1005],f[1005]; //第i个的最小值
signed main(){
int n;
freopen("text.in","r",stdin);
scanf("%d",&n);
for(int i&#61;0;i<n;i&#43;&#43;){
scanf("%d",&a[i]);
}
int cnt&#61;0;
memset(f,0x3f,sizeof(int)*(n&#43;1));
f[0]&#61;-1;//注意边界数据。。
for(int i&#61;0;i<n;i&#43;&#43;){
for(int j&#61;cnt;j>&#61;0;j--){
if(f[j]<a[i]&&f[j&#43;1]>a[i]){
f[j&#43;1]&#61;a[i];
if(j&#61;&#61;cnt)cnt&#43;&#43;;
}
}
}
printf("%d\\n",cnt);
return 0;
}

3.最长公共子序列

https://www.luogu.com.cn/problem/P1439

1.正常想法&#xff1a;

在这里插入图片描述

#include
using namespace std;
#ifdef LOCAL
FILE*fp&#61;freopen("text.in","r",stdin);
#endif
int a[100003],b[100003],s[2][100003];//滚动数组节省空间
int main(){
int t;
scanf("%d",&t);
for(int i&#61;1;i<&#61;t;i&#43;&#43;){
scanf("%d",&a[i]);
}
for(int i&#61;1;i<&#61;t;i&#43;&#43;){
scanf("%d",&b[i]);
}

for(int i&#61;1;i<&#61;t;i&#43;&#43;){
s[i%2][0]&#61;0;
for(int j&#61;1;j<&#61;t;j&#43;&#43;){
if(a[i]&#61;&#61;b[j]){
s[i%2][j]&#61;s[(i&#43;1)%2][j-1]&#43;1;
}else{
s[i%2][j]&#61;max(s[i%2][j-1],s[(i&#43;1)%2][j]);
}
}
}
printf("%d\\n",s[t%2][t]);
return 0;
}

2.这里数据量大&#xff0c;利用不重复&#xff0c;化二公共匹配为按另一个一个中顺序为优先级的一上升子序列为好

#include
#ifdef LOCAL
FILE*fp&#61;freopen("text.in","r",stdin);//文件忘记注释害人不浅&#xff01;&#xff01;
#endif
using namespace std;
map<int,int>m;
int a[100005],f[100005];
signed main(){
int n,te;
scanf("%d",&n);
for(int i&#61;1;i<&#61;n;i&#43;&#43;){
scanf("%d",&te);
m[te]&#61;i;
}
for(int i&#61;1;i<&#61;n;i&#43;&#43;){
scanf("%d",&te);
a[i]&#61;m[te];
}
memset(f&#43;1,0x3f,sizeof(int)*(n&#43;1));
int cnt&#61;0;
for(int i&#61;1;i<&#61;n;i&#43;&#43;){
int l&#61;0,r&#61;cnt,m&#61;(l&#43;r)/2;
while(l<r){
if(f[m]<a[i]&&f[m&#43;1]>&#61;a[i])break;
if(f[m&#43;1]<a[i])l&#61;m&#43;1;
else r&#61;m;
m&#61;(l&#43;r)/2;
}
f[m&#43;1]&#61;a[i];
if(m&#61;&#61;cnt)cnt&#43;&#43;;
}
printf("%d",cnt);
return 0;
}

4.字符串的修改

https://www.luogu.com.cn/problem/P2758


5.海盗分赃

http://acm.hdu.edu.cn/showproblem.php?pid&#61;1538


6.The Uxuhul Voting System

http://acm.hnu.cn/online/?action&#61;problem&type&#61;show&id&#61;10526&courseid&#61;0


附加题&#xff1a;


1.Doing Homework HDU - 1074【状压dp】

http://acm.hdu.edu.cn/showproblem.php?pid&#61;1074

#include
#ifdef LOCAL
FILE*FP&#61;freopen("text.in","r",stdin);
#endif
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
char str[15][102];
int d[15],c[15],s[1<<15],p[1<<15];
int Day(int now){
int sum&#61;0,cnt&#61;0;
while(now){
if(now&1)sum&#43;&#61;c[cnt];
now>>&#61;1;
cnt&#43;&#43;;
}
return sum;
}
void print(int num){
if(num&#61;&#61;0)return;
print(num-(1<<p[num]));
printf("%s\\n",str[p[num]]);
}
signed main(){
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
for(int i&#61;0;i<n;i&#43;&#43;){
scanf("%s%d%d",str[i],&d[i],&c[i]);
}
s[0]&#61;0;
int num&#61;(1<<n)-1;
for(int i&#61;1;i<&#61;num;i&#43;&#43;){
s[i]&#61;INF;
int day&#61;Day(i);
for(int j&#61;0;j<n;j&#43;&#43;){
if(!((i>>j)&1))continue;//再次提醒&#xff1a;&#xff01;单目优先级高
int te&#61;s[i-(1<<j)]&#43;max(0LL,day-d[j]);
if(te<&#61;s[i]){
s[i]&#61;te;
p[i]&#61;j;
}
}
}
printf("%lld\\n",s[num]);
print(num);
}
return 0;
}

2.hdu1024 max sum plus plus

http://acm.hdu.edu.cn/showproblem.php?pid&#61;1024

#include
using namespace std;
#define N 1000005
#define INF 0x3f3f3f3f
int a[N],s[N],p[N];
int t,m,n,ma;
int main(){
while(~scanf("%d%d",&m,&n)){
for(int i&#61;1;i<&#61;n;i&#43;&#43;){
scanf("%d",&a[i]);
}
memset(s,0,sizeof(int)*(n&#43;2));
memset(p,0,sizeof(int)*(n&#43;2));
for(int i&#61;1;i<&#61;m;i&#43;&#43;){
//ma&#61;-INF;
for(int j&#61;i;j<&#61;n;j&#43;&#43;){
s[j]&#61;max(s[j-1],p[j-1])&#43;a[j];
if(j&#61;&#61;i)p[j-1]&#61;-INF,s[j-1]&#61;-INF;
else p[j-1]&#61;max(p[j-2],s[j-1]);
//p[j-1]&#61;ma;//完成上行使命2333
//ma&#61;max(ma,s[j]);//由于s[i-1]是可能更大的&#xff0c;所以要-INF
}
}
printf("%d\\n",*max_element(s&#43;m,s&#43;n&#43;1));
}
}





推荐阅读
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • 在前两篇文章中,我们探讨了 ControllerDescriptor 和 ActionDescriptor 这两个描述对象,分别对应控制器和操作方法。本文将基于 MVC3 源码进一步分析 ParameterDescriptor,即用于描述 Action 方法参数的对象,并详细介绍其工作原理。 ... [详细]
  • 本文详细探讨了KMP算法中next数组的构建及其应用,重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现,帮助读者更好地理解KMP算法的核心原理。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • 本文介绍如何使用Objective-C结合dispatch库进行并发编程,以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码,展示dispatch库的强大功能。 ... [详细]
  • 技术分享:从动态网站提取站点密钥的解决方案
    本文探讨了如何从动态网站中提取站点密钥,特别是针对验证码(reCAPTCHA)的处理方法。通过结合Selenium和requests库,提供了详细的代码示例和优化建议。 ... [详细]
  • 本文探讨了Hive中内部表和外部表的区别及其在HDFS上的路径映射,详细解释了两者的创建、加载及删除操作,并提供了查看表详细信息的方法。通过对比这两种表类型,帮助读者理解如何更好地管理和保护数据。 ... [详细]
  • 主要用了2个类来实现的,话不多说,直接看运行结果,然后在奉上源代码1.Index.javaimportjava.awt.Color;im ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • 本文详细介绍了如何使用 Yii2 的 GridView 组件在列表页面实现数据的直接编辑功能。通过具体的代码示例和步骤,帮助开发者快速掌握这一实用技巧。 ... [详细]
  • 本文详细介绍了Akka中的BackoffSupervisor机制,探讨其在处理持久化失败和Actor重启时的应用。通过具体示例,展示了如何配置和使用BackoffSupervisor以实现更细粒度的异常处理。 ... [详细]
  • 本文详细介绍了Java编程语言中的核心概念和常见面试问题,包括集合类、数据结构、线程处理、Java虚拟机(JVM)、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题,帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • Android LED 数字字体的应用与实现
    本文介绍了一种适用于 Android 应用的 LED 数字字体(digital font),并详细描述了其在 UI 设计中的应用场景及其实现方法。这种字体常用于视频、广告倒计时等场景,能够增强视觉效果。 ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
author-avatar
会长大的幸福7007
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有