Loj 507 接竹竿 題解

来源:https://www.cnblogs.com/201929-whx/archive/2023/01/19/17061181.html
-Advertisement-
Play Games

Loj鏈接:接竹竿 $ {\scr \color {SkyBlue}{\text{Solution}}} $ 題目大意: 給定一個數組,每次加入一種顏色的數,可以取走與它顏色相同的兩個數之間的所有數,問最後取走的所有數中最大和是多少 分析: 第一眼看到的是二分答案,但不知道二分的check()函數怎 ...


Loj鏈接:接竹竿


$ {\scr \color {SkyBlue}{\text{Solution}}} $

題目大意:

給定一個數組,每次加入一種顏色的數,可以取走與它顏色相同的兩個數之間的所有數,問最後取走的所有數中最大和是多少

分析:

第一眼看到的是二分答案,但不知道二分的check()函數怎麼寫。

沒辦法,考慮DP(其實是因為我貪心寫掛了)

DP如果可以,那麼要至少要滿足一下幾個條件:

  1. DP前面的選擇情況不影響後面的選擇情況(前不影響後)
  2. DP可以轉移

時間、空間複雜度等可以以後慢慢優化啦!

 嘗試一下?

嘗試列出轉移方程:

$$dp[i]=max \begin{cases} dp[i-1]& \text{$c_i$}!={c_j}\\ dp[j-1] +   \sum_{k=1}^{i} v_k -    \sum_{k=1}^{j-1} v_k  & \text{$c_i==c_j$} \end{cases}$$ 

這樣我們就列出了一個$O(n^3)$的DP轉移方程。

接下來就考慮優化唄!

優化

  1. 首碼和優化

易發現,DP方程里有很多類似求$\sum_{i}^{j} v_k$的,並且每次DP推方程時都要重新計算一遍

其實,求連續一段值的和,我們可以用首碼和優化啊!

現在方程就是$O(n^2)$的了。

示例代碼(會TLE!):

for(int i=1;i<=n;i++) scanf("%lld",&a[i].y),a[i].y+=a[i-1].y;
for(int i=1;i<=n;i++)
{
    dp[i]=dp[i-1];
    for(int j=1;j<i;j++)
    if(a[i].x==a[j].x) dp[i]=max(dp[i],dp[j-1]+a[i].y-a[j-1].y);
}

考慮進一步優化

發現轉移時,只能找與自己顏色相同的進行轉移,所以可以把每一個顏色記錄下來,省下迴圈過程。

這可以用鏈表或者$ \cal{vector}$ 實現

註意:時間複雜度此時是可以被卡到O(n^2)的!因為並沒有剩下轉移過程,只是省去了枚舉無法轉移情況的時間。

代碼就不放辣QwQ!

再來看看這個轉移方程:

$$dp[i]=max \begin{cases} dp[i-1]& \text{$c_i$}!={c_j}\\ dp[j-1] +   \sum_{k=1}^{i} v_k -    \sum_{k=1}^{j-1} v_k  & \text{$c_i==c_j$} \end{cases}$$ 

我們可以把\cal{dp[i]}的初值賦為$\cal{dp[i-1]}$

那就只要考慮這個:

$$dp[i]=max \begin{cases}  dp[j-1] +   \sum_{k=1}^{i} v_k -    \sum_{k=1}^{j-1} v_k  & \text{$c_i==c_j$} \end{cases}$$ 

用首碼和優化後:

$$dp[i]=max \begin{cases}  dp[j-1] +   summ[i]-    summ[j-1]  & \text{$c_i==c_j$} \end{cases}$$ 

我們稍稍改變一下轉移方程順序:

$$dp[i]=max \begin{cases}   summ[i]+(dp[j-1]  -   summ[j-1])  & \text{$c_i==c_j$} \end{cases}$$ 

換句話說,我們只要求出與$c_i$相等顏色里,$dp[j-1]  -  summ[j-1] $ 最大值

這個可以用一個數組記下來啊!

那麼只要$\cal{O(1)}$,就能完成轉移

時間複雜度:$ \cal{O(n)}$

Code:

#include<bits/stdc++.h>
#define L long long
using namespace std;
struct P{
    int x;
    L y;
}a[1000005];
L dp[1000005],maxx[1000005];
signed main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i].x);
    for(int i=1;i<=k;i++) maxx[i]=-1e18;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i].y),a[i].y+=a[i-1].y;
    for(int i=1;i<=n;i++)
    {
        dp[i]=max(dp[i-1],maxx[a[i].x]+a[i].y);
        maxx[a[i].x]=max(maxx[a[i].x],dp[i-1]-a[i-1].y);
    }
    printf("%lld",dp[n]);
    return 0;
}

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

-Advertisement-
Play Games
更多相關文章
  • 前言 2023年想搭建一套屬於自己的框架,做一個屬於自己想法的項目。這些年工作中一直用公司已有的框架,以前有跟著學習視頻搭建過,但自己真正動手搭建時發現問題還是很多,比如沒有引入Mybatis-plus包之前,項目api test是成功的,引入Mybatis-plus包後就一直啟動不成功,而且異常信 ...
  • 2023-01-19 一、@RequestMapping註解位置 1、書寫在類上面 (1)作用:為當前類設置映射URL (2)註意:不能單獨使用,需要與方法上的@RequestMapping配合使用 2、書寫在方法上面 (1)作用:為當前方法設置映射URL (2)註意:可以單獨使用 3、示例代碼 ( ...
  • 基本數據類型-基礎使用 數值型 整數類型 使用細節 Golang 各整數類型分:有符號和無符號,int uint 的大小和系統是32位還是64位有關 Golang 的整型預設聲明為 int 型 如何在程式查看某個變數的位元組大小和數據類型 (使用較多) Golang 程式中整型變數在使用時,遵守保小不 ...
  • Python如何運行程式 Python解釋器簡介 解釋器是一種讓其他程式運行起來的程式。 Python解釋器將讀取程式,並按照其中的命令執行,得出結果。 解釋器是代碼與機器的電腦硬體之間的軟體邏輯層。 解釋器本身可以用C程式實現,或者一些Java類實現。 程式執行 程式員視角 Python程式僅是 ...
  • 2023-01-19 一、SpringMVC簡介 1、SpringMVC是Spring子框架 2、SpringMVC是Spring為“控制層”提供的基於MVC設計理念的優秀的Web框架,是目前最主流的MVC框架。 3、SpringMVC是非侵入式:可以使用註解讓普通java對象,作為請求處理器(Co ...
  • 安裝Go及開發工具介紹 安裝Go 安裝過程非常簡單,下載自己系統對應的安裝包後直接安裝即可。安裝路徑中包含空格不會對Go環境有影響,在windows系統中,安裝到預設Program Files或Program Files (x86)即可,也可以根據自己需要改變安裝目錄。 安裝完成後,開啟一個新的cm ...
  • 淘汰策略概述 redis作為緩存使用時,在添加新數據的同時自動清理舊的數據。這種行為在開發者社區眾所周知,也是流行的memcached系統的預設行為。 redis中使用的LRU淘汰演算法是一種近似LRU的演算法。 淘汰策略 針對淘汰策略,redis有一下幾種配置方案: 1、noeviction:當觸發內 ...
  • 眾所周知,PDF文檔除了具有較強穩定性和相容性外, 還具有較強的安全性,在工作中可以有效避免別人無意中對文檔內容進行修改。但與此同時,也妨礙了對文檔的正常的修改。這時我們可以將PDF轉為Word文檔進行修改或再編輯。使用軟體將 PDF 文檔轉換為 Word 文檔十分簡單,然而要在轉換時保持佈局甚至字 ...
一周排行
    -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 ...