当前位置:网站首页>Dynamic programming -- linear DP
Dynamic programming -- linear DP
2022-07-06 00:42:00 【Lin Shiliu should work hard】
1. Longest ascending subsequence (LIS)
Plain writing n^2
for(int i=1;i<=n;i++)
{
f[i]=1;
for(int j=1;j<i;j++)
if(a[i]>a[j])
f[i]=max(f[i],f[j]+1);
}
int m=0;
for(int i=1;i<=n;i++) m=max(m,f[i]);
Binary optimization nlogn
int f[N];// The length is i The last bit of the increasing subsequence of
int LIS()
{
int len=0;
f[0]=-0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
int l=0,r=len;
while(l<r)// Find less than a[i] The last number of
{
int mid=l+r+1>>1;
if(f[mid]<a[i])
l=mid;
else
r=mid-1;
}
len=max(len,r+1);
f[r+1]=a[i];
}
return len;
}
2. Longest common subsequence (LCS)
//LCS o(n^2)
int f[N][N];// Before the first sequence i Letters and the first of the second sequence j A subsequence of letters Maximum common subsequence length of
边栏推荐
- Atcoder beginer contest 254 [VP record]
- [groovy] compile time meta programming (compile time method interception | method interception in myasttransformation visit method)
- After Luke zettlemoyer, head of meta AI Seattle research | trillion parameters, will the large model continue to grow?
- Promise
- FFmpeg抓取RTSP图像进行图像分析
- Calculate sha256 value of data or file based on crypto++
- 《强化学习周刊》第52期:Depth-CUPRL、DistSPECTRL & Double Deep Q-Network
- devkit入门
- curlpost-php
- [groovy] XML serialization (use markupbuilder to generate XML data | create sub tags under tag closures | use markupbuilderhelper to add XML comments)
猜你喜欢
Calculate sha256 value of data or file based on crypto++
Search (DFS and BFS)
MCU通过UART实现OTA在线升级流程
Start from the bottom structure and learn the introduction of fpga---fifo IP core and its key parameters
[groovy] JSON serialization (convert class objects to JSON strings | convert using jsonbuilder | convert using jsonoutput | format JSON strings for output)
MYSQL GROUP_ The concat function realizes the content merging of the same ID
Room cannot create an SQLite connection to verify the queries
Classic CTF topic about FTP protocol
Free chat robot API
图解网络:TCP三次握手背后的原理,为啥两次握手不可以?
随机推荐
[Online gadgets] a collection of online gadgets that will be used in the development process
curlpost-php
Go learning --- read INI file
golang mqtt/stomp/nats/amqp
logstash清除sincedb_path上传记录,重传日志数据
Promise
Spark AQE
Atcoder beginer contest 254 [VP record]
Common API classes and exception systems
Model analysis of establishment time and holding time
Multithreading and high concurrency (8) -- summarize AQS shared lock from countdownlatch (punch in for the third anniversary)
Notepad + + regular expression replace String
Comment faire votre propre robot
NLP generation model 2017: Why are those in transformer
OpenCV经典100题
FPGA内部硬件结构与代码的关系
XML配置文件
[groovy] XML serialization (use markupbuilder to generate XML data | create sub tags under tag closures | use markupbuilderhelper to add XML comments)
Codeforces Round #804 (Div. 2)【比赛记录】
时间戳的拓展及应用实例