P1006 [NOIP 2008 提高組] 傳紙條 題解

題目傳送門

前言

每次準備摸魚時都在這道題的界面。

今天有空做做,順便寫一波題解,畢竟估值蹭蹭往下跳。

雙倍經驗:P1004 [NOIP 2000 提高組] 方格取數,P1006 [NOIP 2008 提高組] 傳紙條。

題意簡述

現有一個 m m m n n n 列的矩陣,每個位置上都有一個 [ 0 , 100 ] [0, 100] [0,100] 的整數。

你需要在這個矩陣上走兩遍,第一遍從左上走到右下,這時你只能向下、向右走。第二遍從右下走到左上,這是你只能向上、向左走。要求兩條路徑不能有重合(矩陣的左上角與右下角除外)。

請你求出這兩條路徑所經過的點的總和的最大值。

解題思路

如果你做過 P1004 [NOIP 2000 提高組] 方格取數,那么改一下輸入就能過。

但是為什么 dp 式子不用改?且聽我慢慢道來。

眾所周知,這道題從右下走到左上與從左上做到右下是等價的。所以,我們巧妙的將這道題轉化為了:從左上走到右下,被走過的點不能再走,再從左上走到右下所經過的點的總和的最大值。

于是我們定義 d p i , j , k , l dp_{i, j, k, l} dpi,j,k,l? 為第一遍走到了 ( i , j ) (i,j) (i,j),第二遍走到了 ( k , l ) (k,l) (k,l) 時的最大值。那么狀態轉移方程就是
d p i , j , k , l = { max ? { d p i ? 1 , j , k ? 1 , l , d p i ? 1 , j , k , l ? 1 , d p i , j ? 1 , k ? 1 , l , d p i , j ? 1 , k , l ? 1 } + a i , j + a k , l , if? i ≠ k ∧ j ≠ l ∨ ( i = 1 ∧ j = 1 ∨ i = m ∧ j = n ) ? 1 , if? i = k ∧ j = l ∧ ? ( i = 1 ∧ j = 1 ∨ i = m ∧ j = n ) \begin{equation*} dp_{i, j, k, l} = \begin{cases} \max\{dp_{i - 1, j, k - 1, l}, dp_{i - 1, j, k, l - 1}, dp_{i, j - 1, k - 1, l}, dp_{i, j - 1, k, l - 1}\} + a_{i,j} + a_{k,l}, & \text{if } i \neq k \land j \neq l \lor (i = 1 \land j = 1 \lor i = m \land j = n) \\ -1, & \text{if } i = k \land j = l \land \neg(i = 1 \land j = 1 \lor i = m \land j = n) \end{cases} \end{equation*} dpi,j,k,l?={max{dpi?1,j,k?1,l?,dpi?1,j,k,l?1?,dpi,j?1,k?1,l?,dpi,j?1,k,l?1?}+ai,j?+ak,l?,?1,?if?i=kj=l(i=1j=1i=mj=n)if?i=kj=l?(i=1j=1i=mj=n)??
是不是看起來很復雜?實際上也就只是 LaTeX \LaTeX LATE?X 輸起來復雜。如果懶得看以上形式,直接看代碼就行。

CODE:

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[60][60];
int dp[60][60][60][60];
signed main() {ios::sync_with_stdio(false);ios_base::sync_with_stdio(false);cin.tie(0), cout.tie(0);int m, n;cin >> m >> n;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {cin >> a[i][j];}}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {for (int k = 1; k <= m; k++) {for (int l = 1; l <= n; l++) {dp[i][j][k][l] = max(dp[i - 1][j][k - 1][l], dp[i - 1][j][k][l - 1]);dp[i][j][k][l] = max(dp[i][j - 1][k - 1][l], max(dp[i][j][k][l], dp[i][j - 1][k][l - 1]));dp[i][j][k][l] += a[i][j] + a[k][l];if (i == k && j == l && !(i == 1 && j == 1 || i == m && j == n)) {dp[i][j][k][l] = -114514;}}}}}cout << dp[m][n][m][n];return 0;
}

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

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

相關文章

LLM架構解析:長短期記憶網絡(LSTM)(第三部分)—— 從基礎原理到實踐應用的深度探索

本專欄深入探究從循環神經網絡&#xff08;RNN&#xff09;到Transformer等自然語言處理&#xff08;NLP&#xff09;模型的架構&#xff0c;以及基于這些模型構建的應用程序。 本系列文章內容&#xff1a; NLP自然語言處理基礎詞嵌入&#xff08;Word Embeddings&#xff09…

ffmpeg提取字幕

使用ffmpeg -i test.mkv 獲取視頻文件的字幕流信息如下 Stream #0:4(chi): Subtitle: subrip (srt) (default) Metadata: title : chs Stream #0:5(chi): Subtitle: subrip (srt) Metadata: title : cht Stream #0:6(jpn)…

Python設計模式:構建模式

1. 什么是構建模式 構建模式&#xff08;Builder Pattern&#xff09;是一種創建型設計模式&#xff0c;它允許使用多個簡單的對象一步步構建一個復雜的對象。構建模式通過將構建過程與表示分離&#xff0c;使得同樣的構建過程可以創建不同的表示。換句話說&#xff0c;構建模…

使用 VIM 編輯器對文件進行編輯

一、VIM 的兩種狀態 VIM&#xff08;vimsual&#xff09;是 Linux/UNIX 系列 OS 中通用的全屏編輯器。vim 分為兩種狀態&#xff0c;即命令狀態和編輯狀態&#xff0c;在命令狀態下&#xff0c;所鍵入的字符系統均作命令來處理&#xff1b;而編輯狀態則是用來編輯文本資料&…

GaussDB回調機制深度實踐:從事件驅動到系統集成

GaussDB回調機制深度實踐&#xff1a;從事件驅動到系統集成 一、回調機制核心概念 回調類型矩陣 二、核心實現技術棧 觸發器回調開發 sql -- 創建審計觸發器回調 CREATE OR REPLACE FUNCTION audit_trigger() RETURNS TRIGGER AS $$ BEGININSERT INTO audit_log (operati…

AI小白:AI算法中常用的數學函數

文章目錄 一、激活函數1. Sigmoid2. ReLU&#xff08;Rectified Linear Unit&#xff09;3. Tanh&#xff08;雙曲正切&#xff09;4. Softmax示例代碼&#xff1a;激活函數的實現 二、損失函數1. 均方誤差&#xff08;MSE&#xff09;2. 交叉熵損失&#xff08;Cross-Entropy&…

idea 打不開terminal

IDEA更新到2024.3后Terminal終端打不開的問題_idea terminal打不開-CSDN博客

Python代碼list列表的使用和常用方法及增刪改查

Python代碼list列表的使用和常用方法及增刪改查 提示&#xff1a;幫幫志會陸續更新非常多的IT技術知識&#xff0c;希望分享的內容對您有用。本章分享的是Python基礎語法。前后每一小節的內容是存在的有&#xff1a;學習and理解的關聯性&#xff0c;希望對您有用~ python語法-p…

Open CASCADE學習|讀取點集擬合樣條曲線(續)

問題 上一篇文章已經實現了樣條曲線擬合&#xff0c;但是仍存在問題&#xff0c;Tolerance過大擬合成直線了&#xff0c;Tolerance過大頭尾波浪形。 正確改進方案 1?? 核心參數優化 通過調整以下參數控制曲線平滑度&#xff1a; Standard_Integer DegMin 3; // 最低階…

Python基礎知識點(列表與字典)

列表list[] # list [12,34,56,78] # print(list) """ 1.list可以保存同一類型的數據 或 不同類型的數據 2.list是有序的&#xff0c;所以可以通過[下標]訪問元素 3.list保存重復的值 4.list是可變的&#xff0c;可以添加 刪除元素 """ …

在 Elasticsearch 中使用 Amazon Nova 模型

作者&#xff1a;來自 Elastic Andre Luiz 了解如何在 Elasticsearch 中使用 Amazon Nova 系列模型。 在本文中&#xff0c;我們將討論 Amazon 的 AI 模型家族——Amazon Nova&#xff0c;并學習如何將其與 Elasticsearch 結合使用。 關于 Amazon Nova Amazon Nova 是 Amazon …

MySQL8.0.40編譯安裝(Mysql8.0.40 Compilation and Installation)

MySQL8.0.40編譯安裝 近期MySQL發布了8.0.40版本&#xff0c;與之前的版本相比&#xff0c;部分依賴包發生了變化&#xff0c;因此重新編譯一版&#xff0c;也便于大家參考。 1. 下載源碼 選擇對應的版本、選擇源碼、操作系統 如果沒有登錄或者沒有MySQL官網賬號&#xff0…

python中pyside6多個py文件生成exe

網上見到的教程大多數都是pyinstaller安裝單個py文件,針對多個py文件的打包,鮮有人提及;有也是部分全而多的解釋,讓人目不暇接,本次記錄自己設置一個聲波捕捉界面的打包過程。 1.pycharm中調用pyinstaller打包 參考鏈接:https://blog.csdn.net/weixin_45793544/articl…

Java中使用Function Call實現AI大模型與業務系統的集成?

這個理念實際上很早就出現了&#xff0c;只不過早期的模型推理理解能力比較差&#xff0c;用戶理解深度預測不夠&#xff0c;現在每天的迭代有了改進&#xff0c;逐步引入到我們本身的業務系統&#xff0c;讓AI大模型集成進來管理自身業務功能。當然現在也不是一個什么難事了。…

id 屬性自動創建 js 全局變量

給一個元素設置 id 屬性&#xff0c;它會在 js 中創建全局變量&#xff0c;如 <div class"test" click"test" id"idTest">test</div>test() {console.log(idTest:, window.idTest) }.test {height: 50px;width: 200px;background-c…

Android SELinux權限使用

Android SELinux權限使用 一、SELinux開關 adb在線修改seLinux(也可以改配置文件徹底關閉) $ getenforce; //獲取當前seLinux狀態,Enforcing(表示已打開),Permissive(表示已關閉) $ setenforce 1; //打開seLinux $ setenforce 0; //關閉seLinux二、命令查看sel…

【R語言繪圖】圈圖繪制代碼

繪制代碼 rm(list ls())# 加載必要包 library(data.table) library(circlize) library(ComplexHeatmap) library(rtracklayer) library(GenomicRanges) library(BSgenome) library(GenomicFeatures) library(dplyr)### 數據準備階段 ### # 1. 讀取染色體長度信息 df <- re…

vim 編輯器 使用教程

Vim是一款強大的文本&#xff08;代碼&#xff09;編輯器&#xff0c;它是由Bram Moolenaar于1991年開發完成。它的前身是Bill Joy開發的vi。名字的意義是Vi IMproved。 打開vim&#xff0c;直接在命令行輸入vim即可&#xff0c;或者vim <filename>. Vim分為四種模式&a…

C++20新增內容

C20 是 C 語言的一次重大更新&#xff0c;它引入了許多新特性&#xff0c;使代碼更現代化、簡潔且高效。以下是 C20 的主要新增內容&#xff1a; 1. 概念&#xff08;Concepts&#xff09; 概念用于約束模板參數&#xff0c;使模板編程更加直觀和安全。 #include <concept…

C++中常用的十大排序方法之4——希爾排序

成長路上不孤單&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a; 【&#x1f60a;///計算機愛好者&#x1f60a;///持續分享所學&#x1f60a;///如有需要歡迎收藏轉發///&#x1f60a;】 今日分享關于C中常用的排序方法之4——希爾排序的相…