网站手机版管理链接,企业网站推广价格,贵阳网站建设开发,做网站设计的公司名字今天开始更新动态规划的模板#xff08;动态规划哪有模板呀#xff01;#xff01;#xff01;#xff09;话是这么说#xff0c;但我们经常做题会发现有些题目有些共性#xff0c;我们抽取共性总结出来#xff0c;应付动态规划基础题目还是可以的。
回归正题#xf…今天开始更新动态规划的模板动态规划哪有模板呀话是这么说但我们经常做题会发现有些题目有些共性我们抽取共性总结出来应付动态规划基础题目还是可以的。
回归正题我们今天使用(nlogn)时间复杂度来写模板主要使用Java来写为什么不用c语言呢因为c语言的模板太多了呀
我们解释一下原理吧我们在求最长上升子序列时可以秉持着尽量使得结尾的数最小的思想其实也就是贪心谁让这个贪心比n的平方的普通动规要低时间复杂度呢。我们开个ArrayList不断往里加数字如果链表为空就直接加入不为空如果加入的数字大于链表尾数字我们加入到链表末端如果加入的数字小于链表的末尾数字我们把它找到在链表中第一个大于它的元素的位置把它替换为我们要加入的元素。在这里我们使用写好的二分方法大家要注意我们求的是上升子序列不是不下降子序列一旦我们在ArrayList里边发现一个和我们加入的数字相同的数字我们必须
放弃加入。
模板题目
夏令营动态规划特训 - 【算法模板题】蓝桥勇士 - 蓝桥云课 (lanqiao.cn)
模板 import java.awt.FontFormatException;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.lang.reflect.AnnotatedWildcardType;
import java.math.BigInteger;
import java.sql.SQLIntegrityConstraintViolationException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Spliterator.OfPrimitive;
import java.util.function.IntToDoubleFunction;
import java.util.function.LongBinaryOperator;
import java.util.TreeMap;
import java.util.TreeSet;
import javax.management.relation.InvalidRelationTypeException;
import javax.print.attribute.standard.JobMessageFromOperator;
import javax.print.attribute.standard.JobPriority;
import javax.swing.table.TableModel;
import javax.swing.text.TabSet;
public class Main {public static void main(String[] args) throws IOException {
Scanner scnew Scanner(System.in);
BufferedReader br1new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw1new PrintWriter(System.out);
int asc.nextInt();
int b;
ArrayListInteger al1new ArrayList();
for(b0;ba;b) {int csc.nextInt();if(al1.size()0) {al1.add(c);}if(cal1.get(al1.size()-1)) {al1.add(c);}else {int dCollections.binarySearch(al1,c);if(d0) {int e(-1)*d-1;al1.set(e, c);}}
}
System.out.println(al1.size());}}
