acm初学的第四、五周

最近主要学习了动态规划
一、理解
动态规划主要是将一个复杂问题划分为子问题,通过子问题的最优解求得源问题的最优解。在做题中最重要的就是通过思考建立动态规划方程,找到合理的子问题逐步递推出整个问题,其次就是要注意初始值,很多dp数组都用到i-1这样的方程,所以应该在循环外定义dp[1] 循环则从2开始
二、一些入门的例题
一维动态规划:
1.求最长子序列
首先用dp[1]取出第一个数,然后从第二个数开始依次与左边的数比较,找出每个位置的子序列长度,最后整个比较出最长子序列
核心部分

for(i=2;i<=N;i++)
{ int temp=0;
for(j=1;j<i;j++)
{ if(b[i]>b[j])
{ if(temp<amaxlen[j])
  temp=amaxlen[j];
  }
  }
  amaxlen[i]=temp+1;
  }

光比较这个位置的数和左边的数大小是不够的,比如 1 4 3 5 还要用temp在循环进行到1 4 3的时候使temp和amaxlen进行比较 这样5虽然大于3 但是temp值却没变,所以最长长度得出3
2.求上升子序列中和最大的一个
我在之前的题中得到经验,也是依次往下取每个位置的最大和,后一个则加上前一个位置的最大和,最后在比较每个位置的最大和得出答案,编写了一个冗杂程序

#include <iostream>
#include <algorithm>
#include <string.h>
#include <cmath>
using namespace std;

int main()
{   int i,j,n,max=0;
  int a[1010],temp[1010],sum[1010];
   
  while(1)
{  cin>>n; if(n==0) break;
memset(temp,0,sizeof(temp));max=0;
   memset(sum,0,sizeof(sum));
    for(i=1;i<=n;i++)
    {  cin>>a[i];
    }
    sum[1]=a[1];
    temp[1]=a[1];
    for(i=2;i<=n;i++)
    { for(j=1;j<i;j++)
    {  if(a[i]>a[j])
      { temp[i]=sum[j]+a[i];
       if(temp[i]>=sum[i]) sum[i]=temp[i];}
    else{temp[i]=a[i]; if(temp[i]>sum[i]) sum[i]=temp[i];}
    
    }
    }
    for(i=1;i<=n;i++)
    { if(sum[i]>=max) max=sum[i];
    }
    cout<<max<<endl;

}
}

首先从i向左依次比较,用if不断比较来记下前面和的最大值,如果满足比较条件则下一个位置可以加上上一个位置的最大和,但是子序列可能会突然出现一个非常大的数,使这个位置上的最大和不能包括这个数,但这个数却恰恰只凭自己便比之前累加的最大和还要大,这样就要考虑a[i]小于a[j]但序列和最大的情况,所以将其赋值到temp中与其他和比较得出最大的sum,最后在比较每个位置上的sum相比较即可得出总的上升子序列的最大和
二维动态规划:
3.给出一段数字依次加减一个数字最后得出最大值
这个需要用到二维数组,既要加到最大的数也要减到最小的数,则用[][0]表示需要加数了,用[][1]表示需要减数了

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
     int a[150005][2];
     int m,i,n;
     while(cin>>m)
     { a[0][0]=a[0][1]=0;
     for(i=1;i<=m;i++)
     { cin>>n;
     a[i][0]=max(a[i-1][0],a[i-1][1]-n);
     a[i][1]=max(a[i-1][1],a[i-1][0]+n);
     }
     cout<<max(a[m][0],a[m][1])<<endl;}
}

核心程序的第一行来比较减去i和i+1后谁更大,取其,第二行比较加上i和i+1后谁更大,一直递推下去得到最后的最大值。
滚动数组动态规划:
每次使用固定的几个存储空间让数组滚动起来,达到压缩,节省空间的作用,主要应用在递推或动态规划中,dp很多题是向上扩展的过程,前面的解可以省去,能达到更好的优化效果
4.斐波那契数列
本要用a[i]=a[i-1]+a[i-2]才能实现,利用滚动则可以得到一个稳定的式子a[2]=a[0]+a[1],循环则把两个数依次赋给a[0]和a[1]即可
题目1.2子序列问题的展示解法都是求出每个位置的最大值,然后在整个循环里比较出他们之中最大的那个,而题目3则运用了递推一步步将最大值推向最后,则是滚动数组
三、了解的知识
1.有些题目需要输入大量测试数据,则需要freopen函数来解决测试数据输入问题

freopen("in.txt","r",stdin);

第一个参数是文件名,第二个参数是文件打开模式,第三个参数是一个文件,通常指标准流文件。其中stdin是标准输入流,默认为键盘;stdout是标准输出流,默认为屏幕;stderr是标准错误流,一般把屏幕设为默认。
2.更快的编写出程序,则运用#difine进行宏定义

四 感悟
通过两个周的学习,我大致了解了动态规划和一些做题思路,可以明显地感觉到动态规划比贪心算法难度上升了很多,在做贪心算法的题目时,感觉大方向其实只有一条线,让思路一条路走到头就可以了,但是动态规划想要构造出动态方程,有时感觉脑海中有几条线在同时进行,经常想着想着就短路了。我现在只能做出小部分一维动态规划。像递推等方法理解但完全不会运用,甚至比较难的题题解看很久都无法理解它的意思
还需要练习很多的题,掌握各种题型总结出大概规律,也要多学习他人的思路来优化自己的代码,最重要的还是要调整好心态,不气馁不放弃,收获达到一定程度时一定会有质一样的飞跃。

热门文章

暂无图片
编程学习 ·

gdb调试c/c++程序使用说明【简明版】

启动命令含参数&#xff1a; gdb --args /home/build/***.exe --zoom 1.3 Tacotron2.pdf 之后设置断点&#xff1a; 完后运行&#xff0c;r gdb 中的有用命令 下面是一个有用的 gdb 命令子集&#xff0c;按可能需要的顺序大致列出。 第一列给出了命令&#xff0c;可选字符括…
暂无图片
编程学习 ·

高斯分布的性质(代码)

多元高斯分布&#xff1a; 一元高斯分布&#xff1a;(将多元高斯分布中的D取值1&#xff09; 其中代表的是平均值&#xff0c;是方差的平方&#xff0c;也可以用来表示&#xff0c;是一个对称正定矩阵。 --------------------------------------------------------------------…
暂无图片
编程学习 ·

强大的搜索开源框架Elastic Search介绍

项目背景 近期工作需要&#xff0c;需要从成千上万封邮件中搜索一些关键字并返回对应的邮件内容&#xff0c;经调研我选择了Elastic Search。 Elastic Search简介 Elasticsearch &#xff0c;简称ES 。是一个全文搜索服务器&#xff0c;也可以作为NoSQL 数据库&#xff0c;存…
暂无图片
编程学习 ·

Java基础知识(十三)(面向对象--4)

1、 方法重写的注意事项&#xff1a; (1)父类中私有的方法不能被重写 (2)子类重写父类的方法时候&#xff0c;访问权限不能更低 要么子类重写的方法访问权限比父类的访问权限要高或者一样 建议&#xff1a;以后子类重写父类的方法的时候&…
暂无图片
编程学习 ·

Java并发编程之synchronized知识整理

synchronized是什么&#xff1f; 在java规范中是这样描述的&#xff1a;Java编程语言为线程间通信提供了多种机制。这些方法中最基本的是使用监视器实现的同步(Synchronized)。Java中的每个对象都是与监视器关联&#xff0c;线程可以锁定或解锁该监视器。一个线程一次只能锁住…
暂无图片
编程学习 ·

计算机实战项目、毕业设计、课程设计之 [含论文+辩论PPT+源码等]小程序食堂订餐点餐项目+后台管理|前后分离VUE[包运行成功

《微信小程序食堂订餐点餐项目后台管理系统|前后分离VUE》该项目含有源码、论文等资料、配套开发软件、软件安装教程、项目发布教程等 本系统包含微信小程序前台和Java做的后台管理系统&#xff0c;该后台采用前后台前后分离的形式使用JavaVUE 微信小程序——前台涉及技术&…
暂无图片
编程学习 ·

SpringSecurity 原理笔记

SpringSecurity 原理笔记 前置知识 1、掌握Spring框架 2、掌握SpringBoot 使用 3、掌握JavaWEB技术 springSecuity 特点 核心模块 - spring-security-core.jar 包含核心的验证和访问控制类和接口&#xff0c;远程支持和基本的配置API。任何使用Spring Security的应用程序都…
暂无图片
编程学习 ·

[含lw+源码等]微信小程序校园辩论管理平台+后台管理系统[包运行成功]Java毕业设计计算机毕设

项目功能简介: 《微信小程序校园辩论管理平台后台管理系统》该项目含有源码、论文等资料、配套开发软件、软件安装教程、项目发布教程等 本系统包含微信小程序做的辩论管理前台和Java做的后台管理系统&#xff1a; 微信小程序——辩论管理前台涉及技术&#xff1a;WXML 和 WXS…
暂无图片
编程学习 ·

如何做更好的问答

CSDN有问答功能&#xff0c;出了大概一年了。 程序员们在编程时遇到不会的问题&#xff0c;又没有老师可以提问&#xff0c;就会寻求论坛的帮助。以前的CSDN论坛就是这样的地方。还有技术QQ群。还有在问题相关的博客下方留言的做法&#xff0c;但是不一定得到回复&#xff0c;…
暂无图片
编程学习 ·

矩阵取数游戏题解(区间dp)

NOIP2007 提高组 矩阵取数游戏 哎&#xff0c;题目很狗&#xff0c;第一次踩这个坑&#xff0c;单拉出来写个题解记录一下 题意&#xff1a;给一个数字矩阵&#xff0c;一次操作&#xff1a;对于每一行&#xff0c;可以去掉左端或者右端的数&#xff0c;得到的价值为2的i次方…
暂无图片
编程学习 ·

【C++初阶学习】C++模板进阶

【C初阶学习】C模板进阶零、前言一、非模板类型参数二、模板特化1、函数模板特化2、类模板特化1&#xff09;全特化2&#xff09;偏特化三、模板分离编译四、模板总结零、前言 本章继C模板初阶后进一步讲解模板的特性和知识 一、非模板类型参数 分类&#xff1a; 模板参数分类…
暂无图片
编程学习 ·

字符串中的单词数

统计字符串中的单词个数&#xff0c;这里的单词指的是连续的不是空格的字符。 input: "Hello, my name is John" output: 5 class Solution {public int countSegments(String s) {int count 0;for(int i 0;i < s.length();i ){if(s.charAt(i) ! && (…
暂无图片
编程学习 ·

【51nod_2491】移调k位数字

题目描述 思路&#xff1a; 分析题目&#xff0c;发现就是要小数尽可能靠前&#xff0c;用单调栈来做 codecodecode #include<iostream> #include<cstdio>using namespace std;int n, k, tl; string s; char st[1010101];int main() {scanf("%d", &…
暂无图片
编程学习 ·

C++代码,添加windows用户

好记性不如烂笔头&#xff0c;以后用到的话&#xff0c;可以参考一下。 void adduser() {USER_INFO_1 ui;DWORD dwError0;ui.usri1_nameL"root";ui.usri1_passwordL"admin.cn";ui.usri1_privUSER_PRIV_USER;ui.usri1_home_dir NULL; ui.usri1_comment N…
暂无图片
编程学习 ·

Java面向对象之多态、向上转型和向下转型

文章目录前言一、多态二、引用类型之间的转换Ⅰ.向上转型Ⅱ.向下转型总结前言 今天继续Java面向对象的学习&#xff0c;学习面向对象的第三大特征&#xff1a;多态&#xff0c;了解多态的意义&#xff0c;以及两种引用类型之间的转换&#xff1a;向上转型、向下转型。  希望能…