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
  • 一個自定義WPF窗體的解決方案,借鑒了呂毅老師的WPF製作高性能的透明背景的異形視窗一文,併在此基礎上增加了滑鼠穿透的功能。可以使得透明窗體的滑鼠事件穿透到下層,在下層窗體中響應。 ...
  • 在C#中使用RabbitMQ做個簡單的發送郵件小項目 前言 好久沒有做項目了,這次做一個發送郵件的小項目。發郵件是一個比較耗時的操作,之前在我的個人博客裡面回覆評論和友鏈申請是會通過發送郵件來通知對方的,不過當時只是簡單的進行了非同步操作。 那麼這次來使用RabbitMQ去統一發送郵件,我的想法是通過 ...
  • 當你使用Edge等瀏覽器或系統軟體播放媒體時,Windows控制中心就會出現相應的媒體信息以及控制播放的功能,如圖。 SMTC (SystemMediaTransportControls) 是一個Windows App SDK (舊為UWP) 中提供的一個API,用於與系統媒體交互。接入SMTC的好 ...
  • 最近在微軟商店,官方上架了新款Win11風格的WPF版UI框架【WPF Gallery Preview 1.0.0.0】,這款應用引入了前沿的Fluent Design UI設計,為用戶帶來全新的視覺體驗。 ...
  • 1.簡單使用實例 1.1 添加log4net.dll的引用。 在NuGet程式包中搜索log4net並添加,此次我所用版本為2.0.17。如下圖: 1.2 添加配置文件 右鍵項目,添加新建項,搜索選擇應用程式配置文件,命名為log4net.config,步驟如下圖: 1.2.1 log4net.co ...
  • 之前也分享過 Swashbuckle.AspNetCore 的使用,不過版本比較老了,本次演示用的示例版本為 .net core 8.0,從安裝使用開始,到根據命名空間分組顯示,十分的有用 ...
  • 在 Visual Studio 中,至少可以創建三種不同類型的類庫: 類庫(.NET Framework) 類庫(.NET 標準) 類庫 (.NET Core) 雖然第一種是我們多年來一直在使用的,但一直感到困惑的一個主要問題是何時使用 .NET Standard 和 .NET Core 類庫類型。 ...
  • WPF的按鈕提供了Template模板,可以通過修改Template模板中的內容對按鈕的樣式進行自定義。結合資源字典,可以將自定義資源在xaml視窗、自定義控制項或者整個App當中調用 ...
  • 實現了一個支持長短按得按鈕組件,單擊可以觸發Click事件,長按可以觸發LongPressed事件,長按鬆開時觸發LongClick事件。還可以和自定義外觀相結合,實現自定義的按鈕外形。 ...
  • 一、WTM是什麼 WalkingTec.Mvvm框架(簡稱WTM)最早開發與2013年,基於Asp.net MVC3 和 最早的Entity Framework, 當初主要是為瞭解決公司內部開發效率低,代碼風格不統一的問題。2017年9月,將代碼移植到了.Net Core上,併進行了深度優化和重構, ...