【動態規劃】線性dp——LIS和LCS

參考文章

子序列

一個序列 A = a 1 , a 2 , … , a n A=a_1,a_2,…,a_n Aa1?,a2?,,an? 中任意刪除若干項,剩余的序列叫做 A 的一個子序列。也可以認為是從序列 A 按原順序保留任意若干項得到的序列。(例如:對序列{1,3,5,4,2,6,8,7}來說,序列{3,4,8,7}是它的一個子序列。)

LIS 最長上升子序列

代碼

轉移方程: d p [ i ] = m a x ( d p [ i ] , d p [ j ] + 1 ) dp[i]=max(dp[i],dp[j]+1) dp[i]=max(dp[i],dp[j]+1)

O(n2)

const int N=5010;
int n;
int a[N],dp[N],ans;
signed main(){cin>>n;for(int i=0;i<n;i++){cin>>a[i];}for(int i=0;i<n;i++){dp[i]=1;//自己是一個數列for(int j=0;j<i;j++){if(a[i]>a[j]){//上升dp[i]=max(dp[i],dp[j]+1);//找之前的數列ans=max(dp[i],ans);}}}cout<<ans<<endl;return 0;
}

O(nlogn)

//O(nlogn)做法 
//下降序列
int ans=1,dp[N]={0};
dp[1]=a[1];
for(int k=2;k<=i;k++){if(a[k]<=dp[ans]){//更小的向后取組成序列ans++;dp[ans]=a[k];//下降的序列}else{//跟最后的比不下降 就放前面相當于重開一個序列//dp下降 用greater<>int j=upper_bound(dp+1,dp+1+ans,a[k],greater<int>())-dp;//二分 找第一個小于a[k]的數dp[j]=a[k];//開下降序列}
}
//上升序列
int ans=1,dp[N]={0};
dp[1]=a[1];
for(int k=2;k<=i;k++){if(a[k]>dp[ans]){ans++;dp[ans]=a[k];}else{//dp上升int j=upper_bound(dp+1,dp+1+ans,a[k])-dp;//二分 找第一個大于a[k]的數dp[j]=a[k];}
}

例題

P1020 導彈攔截

構造下降序列找導彈數目,上升序列找系統數目。
二分查找 O(nlogn)做法
細節見代碼。

signed main(){//freopen(".in","r",stdin);//freopen(".out","w",stdout);int i=1;while(cin>>a[i])i++;i--;//能攔截多少導彈int ans=1;dp[1]=a[1];for(int k=2;k<=i;k++){if(a[k]<=dp[ans]){//每一發炮彈都不能高于前一發的高度//比前一發低,記錄數目ans++;dp[ans]=a[k];//構造一個下降的序列}else{//dp下降int j=upper_bound(dp+1,dp+1+ans,a[k],greater<int>())-dp;//二分 找第一個小于a[k]的數 相當于新開一個系統 新開一個下降序列dp[j]=a[k];//開下降序列}}cout<<ans<<endl;//用多少系統int cnt=1;x[1]=a[1];for(int k=2;k<=i;k++){if(x[cnt]<a[k]){//新開一個系統cnt++;x[cnt]=a[k];//x是上升序列}else{int j=lower_bound(x+1,x+cnt+1,a[k])-x;//找第一個大于等于a[k]的系統 能攔截這個炮彈x[j]=a[k];}// for(int m=1;m<=cnt;m++)cout<<x[m]<<' ';// cout<<endl;}cout<<cnt;return 0;
}

P2782 排序+LIS

const int N=2e5+10;
struct fr{int a,b;
}c[N];
int dp[N];
void solve(){int n;cin>>n;forr(i,1,n){cin>>c[i].a>>c[i].b;}sort(c+1,c+1+n,[](fr x,fr y){return x.a<y.a;});//找LISint ans=1;/*//超時forr(i,1,n){dp[i]=1;forr(j,1,i-1){if(c[i].b>c[j].b){dp[i]=max(dp[i],dp[j]+1);ans=max(dp[i],ans);}}}*/dp[1]=c[1].b;forr(i,2,n){if(c[i].b>dp[ans]){ans++;dp[ans]=c[i].b;}else{int j=upper_bound(dp+1,dp+ans+1,c[i].b)-dp;//替換第一個大于c[i].b的dp[j]=c[i].b;}}cout<<ans<<endl;
}

P1091 兩次LIS

const int N=2e5+10;
int dp[N],dpr[N];
void solve(){int n;cin>>n;vector<int>t(n+1);forr(i,1,n){cin>>t[i];}int maxn=0;forr(i,1,n){// dp[i]=1;forr(j,1,i-1){if(t[i]>t[j])dp[i]=max(dp[j]+1,dp[i]);}}reforr(i,1,n){// dpr[i]=1;reforr(j,i+1,n){if(t[i]>t[j])dpr[i]=max(dpr[j]+1,dpr[i]);}}forr(i,1,n){// cout<<dp[i]<<' '<<dpr[i]<<' '<<dp[i]+dpr[i]<<endl;maxn=max(dp[i]+dpr[i]+1,maxn);}cout<<n-maxn<<endl;
}

LCS 最長公共子序列

代碼

在這里插入圖片描述
狀態轉移方程 d p [ i ] [ j ] = m a x ( d p [ i ? 1 ] [ j ] , d p [ i ] [ j ? 1 ] , d p [ i ? 1 ] [ j ? 1 ] + 1 ) dp[i][j]=max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+1) dp[i][j]=max(dp[i?1][j],dp[i][j?1],dp[i?1][j?1]+1),dp是LCS的長度。

forr(i,1,len){forr(j,1,len){if(s1[i-1]==s2[j-1])dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}
}

例題

P1435

回文從前面看后面看都是一樣的,所以思路就是將原字符串和逆轉后的字符串找LCS,就是已經回文的。總長減去回文的就是不回文的。

const int N=1e3+10;
int dp[N][N];
void solve(){string s;cin>>s;string rs=string(s.rbegin(),s.rend());int len=s.size();forr(i,1,len){forr(j,1,len){if(s[i-1]==rs[j-1])dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}cout<<len-dp[len][len];
}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:
http://www.pswp.cn/pingmian/75388.shtml
繁體地址,請注明出處:http://hk.pswp.cn/pingmian/75388.shtml
英文地址,請注明出處:http://en.pswp.cn/pingmian/75388.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

umi框架開發移動端h5

1、官網&#xff1a;https://umijs.org/ 2、創建出來的項目 yarn create umi yarn start3、推薦目錄結構 . ├── config │ └── config.ts ├── public//靜態資源 ├── dist ├── mock │ └── app.ts&#xff5c;tsx ├── src │ ├── .umi │ ├── .um…

《Golang高性能網絡編程:構建低延遲服務器應用》

在本文中&#xff0c;我們將深入探討Golang高性能網絡編程&#xff0c;幫助您構建低延遲服務器應用。我們將介紹Golang的網絡編程特性、優化技巧和實際案例&#xff0c;讓您更好地理解和應用Golang在網絡編程領域的優勢。 高性能網絡編程簡介 什么是Golang高性能網絡編程 高性能…

循環結構- P1217-回文質數-第三十四天

洛谷題單 第三十四天&#xff1a;4.3&#xff08;周四&#xff09; 題目&#xff1a;循環結構–P1217 注意&#xff01;&#xff01;&#xff01;本題的解法在初學階段足矣&#xff0c;使用埃氏篩即可全部AC&#xff08;高級算法&#xff0c;優化時間復雜度&#xff09;&…

github鏡像網站的使用

很多時候我們無法訪問github 那么我們可以網上搜索鏡像網站 比如 https://blog.csdn.net/eytha/article/details/144797222 這里可以找到一些鏡像站 然后直接編輯 c:/user/xxx/.gitconfig 內容如 [user]name xxxxemail xxxxhotmail.com [gui]recentrepo D:/ProjectFolder/t…

論定制開發開源 AI 智能名片 S2B2C 商城小程序源碼在零售變革中的角色與價值

摘要&#xff1a;本文深入探討了新零售中 O2O 模式的特點與局限性&#xff0c;指出其雖有導流作用但難以成為企業轉型適應消費大環境的主力做法。強調解決零售根本問題需依靠大零售概念&#xff0c;包括業態融合、情境創造、分解滲透等。同時引入定制開發開源 AI 智能名片 S2B2…

硬件工程師零基礎入門教程(三)

27.二極管的基本結構 二極管的結構就是一個PN節&#xff0c;導通后肯定會存在壓降&#xff08;硅管≈0.7V&#xff1b;鍺管≈0.3V&#xff09;。 其結構就像一個漏斗結構&#xff0c;普通二極管只能單向導通。 注意&#xff1a;二極管兩端不能直接接大于二極管導通壓降的電壓…

ollama導入huggingface下載的大模型并量化

1. 導入GGUF 類型的模型 1.1 先在huggingface 下載需要ollama部署的大模型 1.2 編寫modelfile 在ollama 里面輸入 ollama show --modelfile <你有的模型名稱> eg: ollama show --modelfile qwen2.5:latest修改其中的from 路徑為自己的模型下載路徑 FROM /Users/lzx/A…

C++基礎系列【35】巧用assert

博主介紹&#xff1a;程序喵大人 35- 資深C/C/Rust/Android/iOS客戶端開發10年大廠工作經驗嵌入式/人工智能/自動駕駛/音視頻/游戲開發入門級選手《C20高級編程》《C23高級編程》等多本書籍著譯者更多原創精品文章&#xff0c;首發gzh&#xff0c;見文末&#x1f447;&#x1f…

【EI檢索】2025年城市設計與規劃國際會議 (CoUDP 2025)

重要信息 會議網址&#xff1a;www.coudp.org 會議時間&#xff1a;2025年9月19-21日 召開地點&#xff1a;中國北京 截稿時間&#xff1a;2025年8月19日 錄用通知&#xff1a;投稿后2周內 收錄檢索&#xff1a;Ei Compendex, SCOPUS 會議簡介 2025年城市設計與規劃…

《實戰AI智能體》MCP對Agent有哪些好處

首先MCP為Agent提供了標準化的方式來接入各種工具和數據源,無論是本地運行的工具,例如通過stdio服務器,還是遠程托管的服務HTTP over SSE服務, Agent都可以通過統一的接口與它們進行交互,極大擴展了第三方工具庫。 例如,在金融領域,Agent 可以接入股票分析的MCP工具。當…

知識圖譜在官網中的本質與部署邏輯

知識圖譜在官網中的本質與部署邏輯 ?1. 知識圖譜不是獨立頁面&#xff0c;而是智能化基礎設施 知識圖譜的最終形態并非一個可見的“圖譜頁面”&#xff0c;而是滲透在官網各交互模塊的AI能力引擎&#xff0c;其核心作用在于&#xff1a; ?后臺&#xff1a;構建實體關系網絡…

藍橋杯沖刺

例題1&#xff1a;握手問題 方法1&#xff1a;數學推理(簡單粗暴&#xff09; 方法2&#xff1a;用代碼實現方法1 #include<iostream> using namespace std; int main() {int result 0;for (int i 1; i < 49; i){for (int j i 1; j < 50; j){//第i個人與第j個…

如何在服務器里備份文件或系統

當我們在企業里&#xff0c;備份文件或者系統是需要經常做的&#xff0c;當我們服務器系統崩潰了或者損壞了&#xff0c;或者我們的存放的工作需求的文件夾損壞丟失&#xff0c;這時候如何我們提前備份了就可以快速回復。 那接下來我們直接上實操&#xff0c;接下來操作是在虛…

Qt實現點擊按鈕彈出側邊框(可用于登錄界面)

Qt實現點擊按鈕彈出側邊框 1、創建界面2、封面按鈕實現2.1 連接信號與槽2.2固定封面按鈕、側邊框及各個標簽位置和頂層顯示封面按鈕2.3創建側邊框狀態并在初始化列表中初始化2.4 側邊框動畫效果實現 3、視頻演示效果4、總結 1、創建界面 封面按鈕樣式表 QPushButton { border…

SQL WHERE 與 HAVING

WHERE 和 HAVING 都是 SQL 中用于篩選數據的子句&#xff0c;但它們有重要的區別 WHERE 子句 在 分組前 過濾數據 作用于 原始數據行 不能使用聚合函數 執行效率通常比 HAVING 高 SELECT column1, column2 FROM table WHERE condition; HAVING 子句 在 分組后 過濾數據 …

表格數據導出為Excel

環境及插件配置&#xff1a;&#xff08;理論上vue2應該也可以使用&#xff0c;沒有試驗過&#xff09; "vue": "^3.2.36", "webpack": "^5.94.0", "webpack-cli": "^5.1.4", "file-saver": "^2.…

Photoshop 2025 Mac中文 Ps圖像編輯軟件

Photoshop 2025 Mac中文 Ps圖像編輯軟件 文章目錄 Photoshop 2025 Mac中文 Ps圖像編輯軟件一、介紹二、效果三、下載 一、介紹 Adobe Photoshop 2025 Mac版集成了多種強大的圖像編輯、處理和創作功能。①強化了Adobe Sensei AI的應用&#xff0c;通過智能摳圖、自動修復、圖像…

rust Send Sync 以及對象安全和對象不安全

開頭&#xff1a;菜鳥小明的疑惑 小明&#xff1a; “李哥&#xff0c;我最近學 Rust&#xff0c;感覺它超級嚴謹&#xff0c;啥 Send、Sync、對象安全、靜態分發、動態分發的&#xff0c;我都搞暈了&#xff01;為啥 Rust 要設計得這么復雜啊&#xff1f;” 小李&#xff0…

JAVA:利用 JSONPath 操作JSON數據的技術指南

1、簡述 JSONPath 是一種強大的工具&#xff0c;用于查詢和操作 JSON 數據。類似于 SQL 的語法&#xff0c;它為處理復雜的 JSON 數據結構提供了簡單且高效的解決方案。? 代碼樣例&#xff1a;https://gitee.com/lhdxhl/springboot-example.git 本文將介紹 JSONPath 的基本…

服務器磁盤卷組緩存cache設置介紹

工具1&#xff1a; storcli a. 確認軟件包是否安裝 [rootlocalhost ~]#rpm -qa | grep storcli storcli-1.21.06-1.noarch 備注&#xff1a;若檢索結果為空&#xff0c;需要安裝對應的軟件安裝包。安裝命令如下&#xff1a; #rpm -ivh storcli-xx-xx-1.noarch.rpm b. 查看邏輯…