热门标签 | 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));
}
}





推荐阅读
  • 本文为Codeforces 1294A题目的解析,主要讨论了Collecting Coins整除+不整除问题。文章详细介绍了题目的背景和要求,并给出了解题思路和代码实现。同时提供了在线测评地址和相关参考链接。 ... [详细]
  • 本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法,并给出了问题的解析和解决方法。详细介绍了问题的背景和规则,并给出了相应的算法解析和实现步骤。通过本文的解析,读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]
  • 本文介绍了P1651题目的描述和要求,以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术,将问题转化为求解差值的问题,并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]
  • FeatureRequestIsyourfeaturerequestrelatedtoaproblem?Please ... [详细]
  • 本文介绍了在开发Android新闻App时,搭建本地服务器的步骤。通过使用XAMPP软件,可以一键式搭建起开发环境,包括Apache、MySQL、PHP、PERL。在本地服务器上新建数据库和表,并设置相应的属性。最后,给出了创建new表的SQL语句。这个教程适合初学者参考。 ... [详细]
  • 本文介绍了九度OnlineJudge中的1002题目“Grading”的解决方法。该题目要求设计一个公平的评分过程,将每个考题分配给3个独立的专家,如果他们的评分不一致,则需要请一位裁判做出最终决定。文章详细描述了评分规则,并给出了解决该问题的程序。 ... [详细]
  • 本文介绍了C++中省略号类型和参数个数不确定函数参数的使用方法,并提供了一个范例。通过宏定义的方式,可以方便地处理不定参数的情况。文章中给出了具体的代码实现,并对代码进行了解释和说明。这对于需要处理不定参数的情况的程序员来说,是一个很有用的参考资料。 ... [详细]
  • 本文介绍了基于c语言的mcs51单片机定时器计数器的应用教程,包括定时器的设置和计数方法,以及中断函数的使用。同时介绍了定时器应用的举例,包括定时器中断函数的编写和频率值的计算方法。主函数中设置了T0模式和T1计数的初值,并开启了T0和T1的中断,最后启动了CPU中断。 ... [详细]
  • 本文介绍了为什么要使用多进程处理TCP服务端,多进程的好处包括可靠性高和处理大量数据时速度快。然而,多进程不能共享进程空间,因此有一些变量不能共享。文章还提供了使用多进程实现TCP服务端的代码,并对代码进行了详细注释。 ... [详细]
  • 本文介绍了解决二叉树层序创建问题的方法。通过使用队列结构体和二叉树结构体,实现了入队和出队操作,并提供了判断队列是否为空的函数。详细介绍了解决该问题的步骤和流程。 ... [详细]
  • 本文介绍了C函数ispunct()的用法及示例代码。ispunct()函数用于检查传递的字符是否是标点符号,如果是标点符号则返回非零值,否则返回零。示例代码演示了如何使用ispunct()函数来判断字符是否为标点符号。 ... [详细]
  • 动态规划算法的基本步骤及最长递增子序列问题详解
    本文详细介绍了动态规划算法的基本步骤,包括划分阶段、选择状态、决策和状态转移方程,并以最长递增子序列问题为例进行了详细解析。动态规划算法的有效性依赖于问题本身所具有的最优子结构性质和子问题重叠性质。通过将子问题的解保存在一个表中,在以后尽可能多地利用这些子问题的解,从而提高算法的效率。 ... [详细]
  • 本文介绍了指针的概念以及在函数调用时使用指针作为参数的情况。指针存放的是变量的地址,通过指针可以修改指针所指的变量的值。然而,如果想要修改指针的指向,就需要使用指针的引用。文章还通过一个简单的示例代码解释了指针的引用的使用方法,并思考了在修改指针的指向后,取指针的输出结果。 ... [详细]
  • Linux环境变量函数getenv、putenv、setenv和unsetenv详解
    本文详细解释了Linux中的环境变量函数getenv、putenv、setenv和unsetenv的用法和功能。通过使用这些函数,可以获取、设置和删除环境变量的值。同时给出了相应的函数原型、参数说明和返回值。通过示例代码演示了如何使用getenv函数获取环境变量的值,并打印出来。 ... [详细]
  • [大整数乘法] java代码实现
    本文介绍了使用java代码实现大整数乘法的过程,同时也涉及到大整数加法和大整数减法的计算方法。通过分治算法来提高计算效率,并对算法的时间复杂度进行了研究。详细代码实现请参考文章链接。 ... [详细]
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社区 版权所有