【Luogu】動態規劃一

P5414 [YNOI2019] 排序 - 洛谷

思路：

可以想到對于任意一個需要換位置的數字，我們不可能換兩次及以上，那么這題就可以轉化為求一個最大和的最長不遞減子序列，最后的答案就是眾和減去這個最大和

代碼：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endlvoid solve()
{int n;cin >> n;vector<int> a(n),b(n,0);int sum = 0;for (int i = 0; i < n; i++){cin >> a[i];for (int j = 0; j < i; j++){if (a[j] <= a[i]){b[i] = max(b[i], b[j]);}}b[i] += a[i];sum += a[i];}int mx = 0;for (int i = 0; i < n; i++){mx = max(mx, b[i]);}cout << sum - mx << endl;
}
signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}

P2690 [USACO04NOV] Apple Catching G - 洛谷

思路：

這一題讓我們求在最多w次換位中能接到的最多蘋果數，一個顯然的想法就是 定義dp[i]為前i個蘋果中能接到的最大值，但是我們發現我們無法判斷當前蘋果能不能選，所以我們還要一維來判斷能不能選當前蘋果，這里我們就定義 dp[i][j] 為前 i 個蘋果中進行了 j 次換位能獲得最大值，這樣我們就能判斷能否選擇了，顯然當換位次數是奇數時，我們就能選 2，否則就是選 1

代碼：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endlvoid solve()
{int t, w;cin >> t >> w;vector<int> a(t+1);for (int i = 1; i <= t; i++){cin >> a[i];a[i]--;}vector<vector<int>> dp(t + 1, vector<int>(w + 1, 0));for (int i = 1; i <= t; i++){for (int j = 0; j <= w; j++){dp[i][j] = dp[i - 1][j];if(j)dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]);dp[i][j] += (a[i] == j % 2);}}int mx = 0;for (int i = 0; i <= w; i++){mx = max(mx, dp[t][i]);}cout << mx;
}
signed main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}

P2904 [USACO08MAR] River Crossing S - 洛谷

思路：

題目告訴我們載n頭牛要ΣM(1~n)的時間，讓我們求載完所有牛最少要多少時間

我們定義dp[i] 為運輸完前 i 頭牛所花費的最短時間

那么轉移方程就是 dp[i] = min(dp[i]，dp[i - j] + sum[j])，其中sum[j]為運輸 j 頭牛耗費的時間

感覺是類完全背包問題

代碼：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endlvoid solve()
{int n, m;cin >> n >> m;vector<int> w(n+1,0),dp(n+1,1000000000);w[0] = 2 * m;for (int i = 1; i <= n; i++){cin >> w[i];w[i] += w[i - 1];}dp[0] = 0;for (int i = 1; i <= n; i++){for (int j = 1; j <= i; j++){dp[i] = min(dp[i], dp[i - j] + w[j]);}}cout << dp[n] - m;
}
signed main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}

P2946 [USACO09MAR] Cow Frisbee Team S - 洛谷

思路：

由于我們要保證他是F的倍數，但是我們肯定不能直接開一個 0 ~ n*F 的bool數組

那我們就需要轉化了，由于我們不需要知道具體的數，我們只需要知道是否是F的倍數，所以我們可以直接開兩個維度，定義dp[i][j]為前i個數組成余F為j的方法有幾種

那么轉移方程就是 dp[i][j] += dp[i-1][j] + dp[i-1][(j -?r[i] + F) % F]，這里 j -?r[i] + F % F代表沒選 r[i]之前的余數是多少，加F這個操作是為了防止其為負數，在大數取模中也可看見

代碼：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
const int MOD = 1e8;
void solve()
{int n, f;cin >> n >> f;vector<int> r(n + 1);vector<vector<int>> dp(n + 1, vector<int>(f+1, 0));for (int i = 1; i <= n; i++){cin >> r[i];r[i] %= f;dp[i][r[i]] = 1;}for (int i = 1; i <= n; i++){for (int j = 0; j <= f - 1; j++){//不選dp[i][j] += dp[i - 1][j];dp[i][j] %= MOD;//選dp[i][j] += dp[i - 1][(j - r[i] + f) % f];dp[i][j] %= MOD;}}cout << dp[n][0] % MOD;
}
signed main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}

P1806 跑步 - 洛谷

思路：

我們定義dp[i][j]為跑了i圈，且最后一次跑了j圈的方案數量，那么轉移就是dp[ i ][ j ] += dp[ i - j ][ k ]

三重循環即可

代碼：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endlvoid solve()
{int n;cin >> n;vector<vector<int>> dp(n + 1, vector<int>(n+1,0));for (int i = 1; i <= n; i++){dp[i][i] = 1;}for (int i = 1; i <= n; i++){for (int j = 1; j < i; j++){for (int k = 1; k < j && j+k <= i; k++){dp[i][j] += dp[i-j][k];}}}int res = 0;for (int i = 1; i < n; i++){res += dp[n][i];}cout << res;
}
signed main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}

P1922 女仆咖啡廳桌游吧 - 洛谷

思路：

由于要確保任意的子樹都滿足桌游和咖啡廳數量一直，所以我們可以直接看葉子節點，只要最下面滿足了，那么上面按照下面的遞推即可

首先可分配的數量為其葉子節點的數量加上自身，那么最多的可選數量就是 sum / 2，然后算出來后往上遞推到節點 1 即可

代碼：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
vector<vector<int>> g(100005);
vector<int> dp(100005,0);
void dfs(int son,int fa)
{int point = 1;for (auto s : g[son]){if (s == fa){continue;}if (g[s].size() == 1){point++;}else{dfs(s, son);dp[son] += dp[s];}}dp[son] += point / 2;
}void solve()
{int n;cin >> n;for (int i = 0; i < n-1; i++){int u, v;cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}dfs(1,1);cout << dp[1];
}
signed main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}

P12175 [藍橋杯 2025 省 Python B] 園藝 - 洛谷

思路：

因為我們要確定間隔，所以我們可以多開一維，定義dp[i][j]前i個樹中間隔為j的最長不遞減子序列

雙重循環即可

代碼：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endlvoid solve()
{int n;cin >> n;vector<int> h(n+1);for (int i = 1; i <= n; i++){cin >> h[i];}vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){dp[i][j] = 1;}}int res = 0;for (int i = 2; i <= n; i++){for (int j = 1; j < i; j++){if (h[i-j] < h[i]){dp[i][j] += dp[i - j][j];res = max(res, dp[i][j]);}}}cout << res;
}
signed main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}

P1564 膜拜 - 洛谷

思路：

這里我們可以利用一個技巧，既然要確保二者的人數差不超過m，那我們就可以視2為-1，那么只要abs(sum) <= m 即可，同時如果 abs(sum) = len 時說明這一串都是同一個數

那么定義 dp[i] 為前 i 個分割的最小數

然后按照上面說的雙重枚舉即可

代碼：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endlvoid solve()
{int n, m;cin >> n >> m;vector<int> dp(n+1,1e9),sum(n+1,0);for (int i = 1; i <= n; i++){int x;cin >> x;sum[i] = sum[i - 1] + (x == 1 ? 1 : -1);}dp[0] = 0;for (int i = 1; i <= n; i++){for (int j = 1; j <= i; j++){if (abs(sum[i] - sum[j-1]) == i-j+1 || abs(sum[i] - sum[j-1]) <= m){dp[i] = min(dp[j-1] + 1, dp[i]);}}}cout << dp[n];
}
signed main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}

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

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

相關文章

什么是管理思維？

什么是管理思維？

管理思維是指在管理活動中形成的系統性、戰略性和創造性的思考方式&#xff0c;幫助個人或團隊更高效地達成目標。它不僅適用于企業管理&#xff0c;也適用于個人成長、項目執行和復雜問題解決。以下是關于管理思維的核心內容&#xff1a; 一、管理思維的核心特征 1. 系統性思…
閱讀更多...
利用TCP+多進程技術實現私聊信息

利用TCP+多進程技術實現私聊信息

服務器&#xff1a; import socket from multiprocessing import Process from threading import Threaduser_dic {}def send_recv(client_conn, client_addr):while 1:# 接收客戶端發送的消息res client_conn.recv(1024).decode("utf-8")print("客戶端發送…
閱讀更多...
Hbuilder 上的水印相機實現方案 (vue3 + vite + hbuilder)

Hbuilder 上的水印相機實現方案 (vue3 + vite + hbuilder)

效果 思路 通過 live-pusher 這個視頻推流的組件來獲取攝像頭拿到視頻的一幀圖片之后&#xff0c;跳轉到正常的 vue 頁面&#xff0c;通過 canvas 來處理圖片水印 源碼 live-pusher 這個組件必須是 nvue 的 至于什么是 nvue&#xff0c;看這個官方文檔吧 https://uniapp.dcl…
閱讀更多...
Spark，IDEA編寫Maven項目

Spark，IDEA編寫Maven項目

IDEA中編寫Maven項目 1.打開IDEA新建項目2.選擇java語言&#xff0c;構建系統選擇Maven 3.IDEA中配置Maven 注&#xff1a;這些文件都是我們老師幫我們在網上找了改動后給我們的&#xff0c;大家可自行在網上查找 編寫代碼測試HDFS連接 1.在之前創建的pom.xml文件中添加下…
閱讀更多...
初識Redis · C++客戶端set和zset

初識Redis · C++客戶端set和zset

目錄 前言&#xff1a; set sadd sismember smembers spop scard sinter sinterstore zset zadd zrange zcard zrem zrank zscore 前言&#xff1a; 前文我們已經介紹了string list hash在Redis-plus-plus的使用&#xff0c;本文我們開始介紹set和zset在redis-plus-pl…
閱讀更多...
sed命令筆記250419

sed命令筆記250419

sed命令筆記250419 sed&#xff08;Stream Editor&#xff09;是 Linux/Unix 系統中強大的流編輯器&#xff0c;主要用于對文本進行過濾和轉換&#xff08;按行處理&#xff09;。它支持正則表達式&#xff0c;適合處理文本替換、刪除、插入等操作。以下是 sed 的詳細解析&…
閱讀更多...
ubuntu-24.04.2-live-server-arm64基于cloud-init實現分區自動擴容（LVM分區模式）

ubuntu-24.04.2-live-server-arm64基于cloud-init實現分區自動擴容（LVM分區模式）

1. 環境 虛擬機鏡像ISO&#xff1a;ubuntu-24.04.2-live-server-arm64.iso 2. 定制cloud-init鏡像 2.1 安裝OS 基于ubuntu-24.04.2-live-server-arm64.iso&#xff0c;通過virt-manager安裝操作系統&#xff0c;語言建議選擇英文&#xff0c;分區選擇基于LVM的自動分區&…
閱讀更多...
vue3專題1------父組件中更改子組件的屬性

vue3專題1------父組件中更改子組件的屬性

理解 Vue 3 中父組件如何引用子組件的屬性是一個很重要的概念。 這里涉及到 defineExpose 和 ref 這兩個關鍵點。 方法&#xff1a;使用 defineExpose 在子組件中暴露屬性&#xff0c;然后在父組件中使用 ref 獲取子組件實例并訪問暴露的屬性。 下面我將詳細解釋這個過程&…
閱讀更多...
數據倉庫分層架構解析：從理論到實戰的完整指南??

數據倉庫分層架構解析：從理論到實戰的完整指南??

數據倉庫分層是構建高效數據體系的核心方法論。本文系統闡述ODS、DWD、DWS、ADS四層架構的設計原理&#xff0c;結合電商用戶行為分析場景&#xff0c;詳解各層功能及協作流程&#xff0c;并給出分層設計的原則與避坑指南&#xff0c;幫助讀者掌握分層架構的落地方法。 一、為什…
閱讀更多...
從零搭建一套前端開發環境

從零搭建一套前端開發環境

一、基礎環境搭建 1.NVM(Node Version Manager)安裝 簡介 nvm&#xff08;Node Version Manager&#xff09; 是一個用于管理多個 Node.js 版本的工具&#xff0c;允許開發者在同一臺機器上輕松安裝、切換和使用不同版本的 Node.js。它特別適合需要同時維護多個項目&#xff…
閱讀更多...
計算機組成原理筆記(十六)——4.1基本算術運算的實現

計算機組成原理筆記(十六)——4.1基本算術運算的實現

計算機中最基本的算術運算是加法運算&#xff0c;加、減、乘、除運算最終都可以歸結為加法運算。 4.1.1加法器 一、加法器的基本單元 加法器的核心單元是 全加器&#xff08;Full Adder, FA&#xff09;&#xff0c;而所有加法器都由 半加器&#xff08;Half Adder, HA&…
閱讀更多...
利用Qt創建一個模擬問答系統

利用Qt創建一個模擬問答系統

界面&#xff1a; 添加了聊天顯示區域&#xff08;QTextEdit&#xff09; 添加了發送按鈕和清空對話按鈕 優化了布局和窗口大小添加了時間戳顯示 2、功能&#xff1a; 支持實時對話可以清空對話歷史 支持按回車發送消息 添加了簡單的關鍵詞匹配響應系統 交互體驗&#x…
閱讀更多...
神經光子渲染：物理級真實感圖像生成——從麥克斯韋方程到深度學習

神經光子渲染：物理級真實感圖像生成——從麥克斯韋方程到深度學習

一、技術背景與核心突破 2025年&#xff0c;神經光子渲染&#xff08;Photonic Neural Rendering, PNR&#xff09;技術通過物理光學方程與神經輻射場的深度融合&#xff0c;在AIGC檢測工具&#xff08;如GPTDetector 5.0&#xff09;的識別準確率從98%降至12%。該技術突破性地…
閱讀更多...
Linux中手動安裝7-Zip軟件文檔

Linux中手動安裝7-Zip軟件文檔

7zip位于EPEL源中&#xff0c;如果服務器可以聯網或者配置了本地EPEL源則可以直接安裝 yum install p7zip p7zip-plugins -y對于無法聯網且沒有配置本地EPEL源的服務器&#xff0c;可以通過官網下載安裝包后&#xff0c;上傳至服務器&#xff0c;手動安裝 ## 下載地址&#x…
閱讀更多...
[密碼學基礎]GM/T 0018-2023 密碼設備應用接口規范深度解析：技術革新與開發者實踐

[密碼學基礎]GM/T 0018-2023 密碼設備應用接口規范深度解析：技術革新與開發者實踐

GM/T 0018-2023 密碼設備應用接口規范深度解析&#xff1a;技術革新與開發者實踐 GM/T 0018-2023《密碼設備應用接口規范》是中國密碼行業的重要標準&#xff0c;于2023年12月4日發布&#xff0c;2024年6月1日正式實施&#xff0c;替代了2012年版標準。該標準旨在規范密碼設備…
閱讀更多...
8.QT-按鈕類控件|Push Button|Radio Button|Check Box|Tool Button(C++)

8.QT-按鈕類控件|Push Button|Radio Button|Check Box|Tool Button(C++)

Push Button 使? QPushButton 表??個按鈕.這也是當前我們最熟悉的?個控件了. QPushButton 繼承? QAbstractButton .這個類是?個抽象類.是其他按鈕的?類 在Qt Designer中也能夠看到這?的繼承關系 屬性說明text按鈕中的?本icon按鈕中的圖標iconSize按鈕中圖標的尺?sh…
閱讀更多...
CFIS-YOLO：面向邊緣設備的木材缺陷檢測輕量級網絡解析

CFIS-YOLO：面向邊緣設備的木材缺陷檢測輕量級網絡解析

論文地址：https://arxiv.org/pdf/2504.11305 目錄 一、論文核心貢獻 二、創新點詳解 2.1 CARAFE動態上采樣 工作原理 優勢對比 2.2 C2f_FNB輕量模塊 計算效率 2.3 Inner-SIoU損失函數 三、實驗驗證 3.1 消融實驗 3.2 對比實驗 四、應用部署 4.1 邊緣設備部署流程…
閱讀更多...
BUUCTF PWN刷題筆記（1-9）

BUUCTF PWN刷題筆記（1-9）

才知道&#xff0c;由于棧對齊&#xff0c;直接動調看棧估計會錯&#xff0c;用cyclic看 1.test_your_nc NC連接一下&#xff0c;這個網站似乎直接訪問是不中的&#xff0c;懷疑是沒開啟web的端口。NC鏈接輸入cat flag就OK了&#xff0c;應該只是讓我這樣的小菜鳥培養自信用的…
閱讀更多...
C#處理網絡傳輸中不完整的數據流

C#處理網絡傳輸中不完整的數據流

1、背景 在讀取byte數組的場景&#xff08;例如&#xff1a;讀取文件、網絡傳輸數據&#xff09;中&#xff0c;特別是網絡傳輸的場景中&#xff0c;非常有可能接收了不完整的byte數組&#xff0c;在將byte數組轉換時&#xff0c;因字符的缺失/增多&#xff0c;轉為亂碼。如下…
閱讀更多...
PostgreSQL 用戶資源管理

PostgreSQL 用戶資源管理

PostgreSQL 用戶資源管理 PostgreSQL 提供了多種機制來管理和限制用戶對數據庫資源的使用&#xff0c;以下是全面的資源管理方法&#xff1a; 1 連接限制 1.1 限制最大連接數 -- 在 postgresql.conf 中設置 max_connections 100 -- 全局最大連接數-- 為特定用戶設置連接限…
閱讀更多...
最新文章

Copyright @ 2022~2023