CF 1927

来源:https://www.cnblogs.com/wmmdbk/p/18012153/cf1972
-Advertisement-
Play Games

G 題面 定義\({{dp_i}_j}_k\)為考慮完第i個點,最左邊沒有染色的點為\(j\),最右邊沒有染色的點為\(k\)的最小數量。 考慮轉移(用自己更新別人) 如果不用\(i\),直接轉移到\({{dp_{i+1}}_j}_k\)。 如果向左噴,\(k\)為\(max({i+1,k})\), ...


G
題面
定義\({{dp_i}_j}_k\)為考慮完第i個點,最左邊沒有染色的點為\(j\),最右邊沒有染色的點為\(k\)的最小數量。
考慮轉移(用自己更新別人)
如果不用\(i\),直接轉移到\({{dp_{i+1}}_j}_k\)

如果向左噴,\(k\)\(max({i+1,k})\),判斷能噴到的位置

  • \(j\)更靠左,\(j\)將變成\(max({i+2,k+1})\)\(i+1\)的下一個或\(k\)的下一個將為最左邊沒有染色的);
  • 否則,\(j\)將不變。

如果向右噴,\(k\)\(max({i+a_i-1,k})\),判斷能噴到的位置

  • \(j\)更靠左,\(j\)將變成\(max({i+a_i,k+1})\)\(i+a_i-1\)的下一個或\(k\)的下一個將為最左邊沒有染色的);
  • 否則,\(j\)將不變。
點擊查看代碼
#include<bits/stdc++.h>

#define int long long

using namespace std;

int t;
int n;
int a[105];
int q[105];
int h[105];
int dp[105][105][105];

void mx(int &a,int b){
	a = min(a,b);
}

void qwq(){
	
	cin >> n;
	for(int i = 1;i <= n;++ i){
		cin >> a[i];
		q[i] = max(1ll,i-a[i]+1);
		h[i] = min(n,i+a[i]-1);
	}
	
	memset(dp,0x3f,sizeof(dp));
	dp[0][1][0] = 0;
	
	for(int i = 0;i < n;++ i){
		
		for(int j = 1;j <= n+1;++ j)
			for(int k = 0;k <= n;++ k)
				mx(dp[i+1][j][k],dp[i][j][k]);
		
		for(int j = 1;j <= n+1;++ j){
			for(int k = 0;k <= n;++ k){
				if(q[i+1] <= j){
					mx(dp[i+1][max(i+2,k+1)]
					[max(i+1,k)],dp[i][j][k]+1);
				}
				else{
					mx(dp[i+1][j][max(i+1,k)],
					dp[i][j][k]+1);
				}
			}
		}
		
		for(int j = 1;j <= n+1;++ j){
			for(int k = 0;k <= n;++ k){
				if(i+1 <= j){
					mx(dp[i+1][max(h[i+1]+1,j)]
					[max(h[i+1],k)],
					dp[i][j][k]+1);
				}
				else{
					mx(dp[i+1][j][max(h[i+1],k)]
					,dp[i][j][k]+1);
				}
			}
		}
		
	}
	
	cout << dp[n][n+1][n] << endl;
	
}

signed main(){
	
	cin >> t;
	while(t--) qwq();
	
	return 0;
	
}

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

-Advertisement-
Play Games
更多相關文章
  • 開心一刻 今天我突然頓悟了,然後跟我媽聊天 我:媽,我發現一個餓不死的辦法 媽:什麼辦法 我:我先養個狗,再養個雞 媽:然後了 我:我拉的狗吃,狗拉的雞吃,雞下的蛋我吃,如此反覆,我們三都餓不死 媽:你整那麼多中間商幹啥,你就自己拉的自己吃得了,還省事 我又頓悟了,回到:也是啊 說句很重要的心裡話: ...
  • 寫在前面 和大家不太一樣,我覺得今年的自己更加relax,沒有親戚要走,沒有朋友相聚,也沒有很好的哥們要去敘舊,更沒有無知的相親,甚至可以這麼說沒有那些閑得慌的鄰居。 也可以說是從今天開始,算是可以進入自己的小世界,做自己想做的事,看看書,學習一下。 生活的精髓在於善待自己,用心感受每一刻的歡愉與寧 ...
  • 前言 上回說到,利用vite載入不同mode下的配置文件,可以實現不同運行環境下的參數配置。在前端應用中經常使用到Websocket,其地址同樣可以在.env中間中配置。 代碼 vite.config.ts代碼的執行是在createApp之前,不可以在vite.config.ts中使用例如pinia ...
  • 步驟 根目錄新建.env.development和.env.production文件 package.json配置啟動參數 vite命令啟動項目時,指定mode參數,載入vite.config.ts文件。 "dev": "vite --host 0.0.0.0 --port 8093 --mode ...
  • 找半天沒找到相關的內容,自己搗鼓出來的,記錄一下。(比較可惜的是只能獲取靜態圖片,動態壁紙就不知道了咋弄了) uniapp的話還可以參考一下如何用NJS獲取手機桌面壁紙? - DCloud問答下麵DCloud_heavensoft 大佬的一個回答 : “Native.js很多類型沒有。用uts可以  ...
  • 前言 以前使用的都是預設的博客園主題,最近剛好有空,著手定製以下自己的博客園主題。最終效果參考當前的博客,如果看不到則需要在博客園首頁頭像處懸停關閉簡潔模式 思路是儘量保持原有結構,不進行破壞性改動,以 css 樣式為主 本主題是輕量化的,只是在原有基礎上微調樣式。如有需要更豐富功能的可以自己搜索博 ...
  • 迴首 在 零基礎入門Vue之夢開始的地方——插值語法 我記錄了v-bind、v-on、v-model的學習 在 零基礎入門Vue之To be or not to be——條件渲染 我記錄了v-if、v-else-if、v-else、v-show的學習 在 零基礎入門Vue之影分身之術——列表渲染&渲 ...
  • Rich庫的功能就像它的名字一樣,使Python編程更加豐富(rich),它幫助開發者在控制台(命令行)輸出中創建豐富、多彩和具有格式化的文本。 本篇總結瞭如何使用Rich庫讓我們的命令行工具更加美觀。 1. 安裝 通過pip安裝: pip install rich 使用下麵的命令驗證是否安裝成功。 ...
一周排行
    -Advertisement-
    Play Games
  • 在C#中使用SQL Server實現事務的ACID(原子性、一致性、隔離性、持久性)屬性和使用資料庫鎖(悲觀鎖和樂觀鎖)時,你可以通過ADO.NET的SqlConnection和SqlTransaction類來實現。下麵是一些示例和概念說明。 實現ACID事務 ACID屬性是事務處理的四個基本特征, ...
  • 我們在《SqlSugar開發框架》中,Winform界面開發部分往往也用到了自定義的用戶控制項,對應一些特殊的界面或者常用到的一些局部界面內容,我們可以使用自定義的用戶控制項來提高界面的統一性,同時也增強了使用的便利性。如我們Winform界面中用到的分頁控制項、附件顯示內容、以及一些公司、部門、菜單的下... ...
  • 在本篇教程中,我們學習瞭如何在 Taurus.MVC WebMVC 中進行數據綁定操作。我們還學習瞭如何使用 ${屬性名稱} CMS 語法來綁定頁面上的元素與 Model 中的屬性。通過這些步驟,我們成功實現了一個簡單的數據綁定示例。 ...
  • 是在MVVM中用來傳遞消息的一種方式。它是在MVVMLight框架中提供的一個實現了IMessenger介面的類,可以用來在ViewModel之間、ViewModel和View之間傳遞消息。 Send 接受一個泛型參數,表示要發送的消息內容。 Register 方法用於註冊某個對象接收消息。 pub ...
  • 概述:在WPF中,通過EventHandler可實現基礎和高級的UI更新方式。基礎用法涉及在類中定義事件,併在UI中訂閱以執行更新操作。高級用法藉助Dispatcher類,確保在非UI線程上執行操作後,通過UI線程更新界面。這兩種方法提供了靈活而可靠的UI更新機制。 在WPF(Windows Pre ...
  • 概述:本文介紹了在C#程式開發中如何利用自定義擴展方法測量代碼執行時間。通過使用簡單的Action委托,開發者可以輕鬆獲取代碼塊的執行時間,幫助優化性能、驗證演算法效率以及監控系統性能。這種通用方法提供了一種便捷而有效的方式,有助於提高開發效率和代碼質量。 在軟體開發中,瞭解代碼執行時間是優化程式性能 ...
  • 概述:Cron表達式是一種強大的定時任務調度工具,通過配置不同欄位實現靈活的時間規定。在.NET中,Quartz庫提供了簡便的方式配置Cron表達式,實現精準的定時任務調度。這種靈活性和可擴展性使得開發者能夠根據需求輕鬆地制定和管理定時任務,例如每天備份系統日誌或其他重要操作。 Cron表達式詳解 ...
  • 概述:.NET提供多種定時器,如System.Windows.Forms.Timer適用於UI,System.Web.UI.Timer用於Web,System.Diagnostics.Timer用於性能監控,System.Threading.Timer和System.Timers.Timer用於一般 ...
  • 問題背景 有同事聯繫我說,在生產環境上,訪問不了我負責的common服務,然後我去檢查common服務的health endpoint, 沒問題,然後我問了下異常,timeout導致的System.OperationCanceledException。那大概率是客戶端的問題,會不會是埠耗盡,用ne ...
  • 前言: 在本篇 Taurus.MVC WebMVC 入門開發教程的第四篇文章中, 我們將學習如何實現數據列表的綁定,通過使用 List<Model> 來展示多個數據項。 我們將繼續使用 Taurus.Mvc 命名空間,同時探討如何在視圖中綁定並顯示一個 Model 列表。 步驟1:創建 Model ...