P1352 沒有上司的舞會+P1122 最大子樹和(樹形DP入門)

来源:https://www.cnblogs.com/lzyan-blog/archive/2023/01/18/17059005.html
-Advertisement-
Play Games

前言 今日偶然打開 $oi-wiki$,發現樹形 $DP$ 例題正好是之前在洛谷上鴿著的一道題。所以...... $\color{red}{很高興以這樣的方式認識你,樹形 DP !}$ 這例題造的太好了,簡直是無痛入門(感動.jpg) P1352 沒有上司的舞會 題目傳送門~ 思路剖析 狀態定義 $ ...


前言

今日偶然打開 \(oi-wiki\),發現樹形 \(DP\) 例題正好是之前在洛谷上鴿著的一道題。所以......

\(\color{red}{很高興以這樣的方式認識你,樹形 DP !}\)

這例題造的太好了,簡直是無痛入門(感動.jpg)

P1352 沒有上司的舞會

題目傳送門~

思路剖析

狀態定義

\(dp_i\) 表示的是以 \(i\) 為根節點的子樹所獲得的最大價值。

由於每個節點代表著一位人物,有來與不來兩種狀態,所以再加一維狀態變數。

\(dp_{i,0}\) 表示以 \(i\) 為根節點的子樹所能獲得的最大價值,且這位人物沒來。 \(dp_{i,1}\) 則對應來了的狀態。

狀態轉移方程

 現在有個周年慶宴會,宴會每邀請來一個職員都會增加一定的快樂指數 r_i。
 但是呢,如果某個職員的直接上司來參加舞會了,那麼這個職員就無論如何也不肯來參加舞會了。

根據題意描述,容易得出狀態轉移方程:

\(dp_{i,0} += max (dp_{j,0},dp_{j,1})\)

\(dp_{i,1} += dp_{j,0}\)

\(j\) 指的是 \(i\) 的子節點,且顯然 \(dp_{i,1}\) 的初始值為 \(r_i\)

code

點擊查看代碼
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,a[6005];
int head[6005],nex[6005],edge[6005],tot;
int vis[6005],dp[6005][2];
void dfs(int x){
	dp[x][1]=a[x];
	for(int i=head[x];i;i=nex[i]){
		int y=edge[i];
		dfs(y);
		dp[x][1]+=dp[y][0];
		dp[x][0]+=max(dp[y][0],dp[y][1]);
	}
	return;
} 
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<n;i++){
		int l,k;
		scanf("%d%d",&l,&k);
		nex[++tot]=head[k];
		head[k]=tot;
		edge[tot]=l;
		vis[l]=1;
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			dfs(i);
			cout<<max(dp[i][0],dp[i][1])<<endl;
			return 0;
		}
	}
}

P1122 最大子樹和

題目傳送門~

思路剖析

誰是根節點

由於這題是無向圖(但由於以 \(n-1\) 條邊相連接,所以本質與樹並無太大區別),所以要討論以誰作為根節點。

根節點之所以重要,是因為在遞歸過程中,我們已經預設根節點所代表的那束花已經被保留了,但根節點代表的花不一定在最優解的集合之中。

仔細模擬後,不難發現,對於以 \(i\) 為根節點的子樹,\(dp_i\) 往下為最優解,而往上由於還未更新,因此相當於剪去 \(dp_i\) 與其根節點的枝椏。

進一步推理,無論通過哪個節點作為根節點,再遞歸的過程中,其實已經變相枚舉了將其剪去的種種情況,所以,只需要在過程中取最優解即可。

狀態定義+狀態轉移方程

這點比較好理解,所以合併在一起闡述。

\(dp_i\) 表示以 \(i\) 為根節點的子樹所獲得的最大美麗值。

顯然有

\(dp_i+=max(dp_j,0)\)

\(j\) 為子節點,當其所帶來的價值為負數時,不如直接剪掉。

code

有幾處雷點在註釋中標記出來了(都是血淚教訓啊QAQ)

點擊查看代碼
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,ans=-0x3f3f3f3f;//答案可能為負!要初始化為負無窮
int head[16005],nex[35005],edge[35005],tot;//由於是雙向邊,所以空間要開雙倍
int dp[16005],vis[16005];
void dfs(int x){
	vis[x]=1;//不要在迴圈內標記,否則標記不到根節點本身。
	for(int i=head[x];i;i=nex[i]){
		int y=edge[i];
		if(vis[y]) continue;
		dfs(y);
		if(dp[y]<=0) continue;
		dp[x]+=dp[y]; 
	}
	ans=max(ans,dp[x]);
	return;
} 
void add(int l,int k) {nex[++tot]=head[k],head[k]=tot,edge[tot]=l;}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&dp[i]);
	for(int i=1;i<n;i++){
		int l,k;
		scanf("%d%d",&l,&k);
		add(l,k);
		add(k,l);
	}
	dfs(1);
	cout<<ans<<endl;
	return 0;
}

\(7、8\) 道,(‾◡◝)。

加油!


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 使用數據處理函數 函數 與其他大多數電腦語言一樣,SQL支持利用函數來處理數據。函數一般是在數據上執行的,它給數據的轉換和處理提供了方便。 註意: 函數沒有SQL的可移植性強:能運行在多個系統上的代碼稱為可移植的(portable)。函數的可移植性卻不強。幾乎每種主要的DBMS的實現都支持其他實現 ...
  • 京東物流:康睿 姚再毅 李振 劉斌 王北永 說明:以下全部均基於elasticsearch8.1 版本 一.跨集群檢索 - ccr 官網文檔地址: https://www.elastic.co/guide/en/elasticsearch/reference/8.1/modules-cross-cl ...
  • 前言 做線上幀率監控上報時,少不了需要弄明白如何通過代碼獲取實時幀率的需求,這篇文章通過圖解配合Flutter性能調試工具的方式一步步通俗易懂地讓你明白獲取幀率的基礎知識,以後再也不愁看不懂調試工具上指標了。 說說 List<FrameTiming> Flutter 中通過如下方式監聽幀率,addT ...
  • 華為運動健康服務(HUAWEI Health Kit)6.9.0版本新鮮出爐啦! 一文瞭解新增功能,快來一起加入Health Kit生態大家庭! 一、更豐富:睡眠呼吸記錄健康數據開放 呼吸機是用於為患者提供或增加肺通氣的常用醫療器械,目前越來越多的家用呼吸機被用於緩解人們在日常睡眠過程中的打鼾、睡眠 ...
  • 2023-01-17 一、Servlet底層源碼分析 1、Servlet結構圖 說明:HttpServlet繼承了GenericServlet類,GenericServlet實現了“ServletConfig”和“Servlet”兩個介面,因此所以要實現一個Servlet直接就可以繼承HttpSer ...
  • 2023-01-13 一、基本功 (1)工程結構管理 掌握企業環境的搭建和管理 (2)java開發規範 P3C開發規約 (3)高併發及網路編程 需要考慮性能瓶頸 (4)底層源碼分析 二、互聯網常用技術——分散式 1、NoSQL資料庫:是提升數據訪問效率的優先選擇。 訪問效率的提升:Redis、Mon ...
  • 1. API 網關誕生背景 前言 API 經濟生態鏈已經在全球範圍覆蓋, 絕大多數企業都已經走在數字化轉型的道路上,API 成為企業連接業務的核心載體, 並產生巨大的盈利空間。快速增長的 API 規模以及調用量,使得企業 IT 在架構上、模式上面臨著更多的挑戰。 API 是什麼 API 網關是一個服 ...
  • CAP特性 ​ CAP理論是在設計分散式系統的過程中,處理數據一致性問題時必須考慮的理論,一個分散式系統最多只能同時滿足一致性(Consistence)、可用性(Availability)和分區容錯性(Partition tolerance)這三項中的兩項。 2000年7月Eric Brewer教授 ...
一周排行
    -Advertisement-
    Play Games
  • 下麵是一個標準的IDistributedCache用例: public class SomeService(IDistributedCache cache) { public async Task<SomeInformation> GetSomeInformationAsync (string na ...
  • 這個庫提供了在啟動期間實例化已註冊的單例,而不是在首次使用它時實例化。 單例通常在首次使用時創建,這可能會導致響應傳入請求的延遲高於平時。在註冊時創建實例有助於防止第一次Request請求的SLA 以往我們要在註冊的時候實例單例可能會這樣寫: //註冊: services.AddSingleton< ...
  • 最近公司的很多項目都要改單點登錄了,不過大部分都還沒敲定,目前立刻要做的就只有一個比較老的項目 先改一個試試手,主要目標就是最短最快實現功能 首先因為要保留原登錄方式,所以頁面上的改動就是在原來登錄頁面下加一個SSO登錄入口 用超鏈接寫的入口,頁面改造後如下圖: 其中超鏈接的 href="Staff ...
  • Like運算符很好用,特別是它所提供的其中*、?這兩種通配符,在Windows文件系統和各類項目中運用非常廣泛。 但Like運算符僅在VB中支持,在C#中,如何實現呢? 以下是關於LikeString的四種實現方式,其中第四種為Regex正則表達式實現,且在.NET Standard 2.0及以上平... ...
  • 一:背景 1. 講故事 前些天有位朋友找到我,說他們的程式記憶體會偶發性暴漲,自己分析了下是非托管記憶體問題,讓我幫忙看下怎麼回事?哈哈,看到這個dump我還是非常有興趣的,居然還有這種游戲幣自助機類型的程式,下次去大玩家看看他們出幣的機器後端是不是C#寫的?由於dump是linux上的程式,剛好win ...
  • 前言 大家好,我是老馬。很高興遇到你。 我們為 java 開發者實現了 java 版本的 nginx https://github.com/houbb/nginx4j 如果你想知道 servlet 如何處理的,可以參考我的另一個項目: 手寫從零實現簡易版 tomcat minicat 手寫 ngin ...
  • 上一次的介紹,主要圍繞如何統一去捕獲異常,以及為每一種異常添加自己的Mapper實現,並且我們知道,當在ExceptionMapper中返回非200的Response,不支持application/json的響應類型,而是寫死的text/plain類型。 Filter為二方包異常手動捕獲 參考:ht ...
  • 大家好,我是R哥。 今天分享一個爽飛了的面試輔導 case: 這個杭州兄弟空窗期 1 個月+,面試了 6 家公司 0 Offer,不知道問題出在哪,難道是杭州的 IT 崩盤了麽? 報名面試輔導後,經過一個多月的輔導打磨,現在成功入職某上市公司,漲薪 30%+,955 工作制,不咋加班,還不捲。 其他 ...
  • 引入依賴 <!--Freemarker wls--> <dependency> <groupId>org.freemarker</groupId> <artifactId>freemarker</artifactId> <version>2.3.30</version> </dependency> ...
  • 你應如何運行程式 互動式命令模式 開始一個互動式會話 一般是在操作系統命令行下輸入python,且不帶任何參數 系統路徑 如果沒有設置系統的PATH環境變數來包括Python的安裝路徑,可能需要機器上Python可執行文件的完整路徑來代替python 運行的位置:代碼位置 不要輸入的內容:提示符和註 ...