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
  • 一:背景 1. 講故事 年前遇到了好幾例托管堆被損壞的案例,有些運氣好一些,從被破壞的托管堆記憶體現場能觀測出大概是什麼問題,但更多的情況下是無法做出準確判斷的,原因就在於生成的dump是第二現場,借用之前文章的一張圖,大家可以理解一下。 為了幫助更多受此問題困擾的朋友,這篇來整理一下如何 快狠準 的 ...
  • 前言 .NET6 開始,.NET Croe API 項目取消了 Startup.cs 文件,在 Program.cs 文件的 Main 函數中完成服務的註冊和中間件管道的管理。但當我們項目引入更多包的時候,Program.cs 文件也會看起來很臃腫。 而且,我們不只會有一個後端項目,為了方便快速創建 ...
  • 目錄 背景 get 與 post 的區別 所有介面都用 post 請求? 背景 最近在逛知乎的時候發現一個有趣的問題:公司規定所有介面都用 post 請求,這是為什麼? 看到這個問題的時候其實我也挺有感觸的,因為我也曾經這樣問過我自己。在上上一家公司的時候接到一個項目是從零開始搭建一個微服務,當時就 ...
  • *以下內容為本人的學習筆記,如需要轉載,請聲明原文鏈接 微信公眾號「englyf」https://mp.weixin.qq.com/s/2GFLTstDC7w6u3fTJxflNA 本文大概 1685 個字,閱讀需花 6 分鐘內容不多, 但也花了一些精力如要交流, 歡迎關註我然後評論區留言 謝謝你的 ...
  • 在新版本的pandas中,上述代碼會引起警告,建議改成SQLAlchemy connectable(engine/connection),後續代碼將引入這種升級的連接方式。 ...
  • 幾乎所有的高級編程語言都有自己的垃圾回收機制,開發者不需要關註記憶體的申請與釋放,Python 也不例外。Python 官方團隊的文章 https://devguide.python.org/internals/garbage-collector 詳細介紹了 Python 中的垃圾回收演算法,本文是這篇 ...
  • 如果您想查找高於或低於平均值的數字,可以不必計算該平均值,就能查看更高或更低的值。通過Java應用程式,可以自動突出顯示這些數字。除了快速突出顯示高於或低於平均值的值外,您還可以查看高於或低於的值的個數。現在讓我們看看如何在 Java應用程式中實現此操作。 引入jar包 導入方法1: 手動引入。將  ...
  • 第一種方式:使用{} firstDict = {"name": "wang yuan wai ", "age" : 25} 說明:{}為創建一個空的字典對象 第二種方式:使用fromkeys()方法 second_dict = dict.fromkeys(("name", "age")) #valu ...
  • 在golang中可以使用a := b這種方式將b賦值給a,只有當b能進行深拷貝時a與b才不會互相影響,否則就需要進行更為複雜的深拷貝。 下麵就是Go賦值操作的一個說明: Go語言中所有賦值操作都是值傳遞,如果結構中不含指針,則直接賦值就是深度拷貝;如果結構中含有指針(包括自定義指針,以及切片,map ...
  • 本文結合京東監控埋點場景,對解決樣板代碼的技術選型方案進行分析,給出最終解決方案後,結合理論和實踐進一步展開。通過關註文中的技術分析過程和技術場景,讀者可收穫一種樣板代碼思想過程和解決思路,並對Java編譯器底層有初步瞭解。 ...