題目鏈接：點擊查看

題目大意：給出一個長度為 $n$ 的數列，現在需要將其劃分成 $k$ 段，使得貢獻和最小

對于每段區間 $[l,r]$ 的貢獻為，其中每個數字，其最后一次出現的位置減去其首次出現的位置

輸出最小貢獻

題目分析：區間劃分，經典的 $dp$ 問題，$d{p}_{i,j}$ 代表前 $i$ 個數劃分為 $j$ 個區間的最優解，兩種轉移方程：

$d{p}_{i,j}=min(d{p}_{i?1,j}+(a_i屬于上一段的貢獻),d{p}_{i?1,j?1}+(a_i獨成一段的貢獻))$

$d{p}_{i,j}=min(d{p}_{k,j?1}+val(k+1,i))$

以上，第一種轉移方程的時間復雜度是 $O(n?m)$ 的，缺點是無法知曉最后一段區間的起點

第二種轉移方程的時間復雜度是 $O(n?n?m)$ 的，可以知曉最后一段區間的起點

就本題而言，我們只能選擇第二種轉移方程，所以考慮利用數據結構優化掉一維 $n$

不難發現對于動態規劃的第二維是可以滾動的，所以不妨在固定第二維后，將第一維的信息扔進線段樹里，這樣就可以 $O(logn)$ 去維護區間最小值了，此時線段樹中的每個節點實質上維護的是 $d{p}_i+val(i+1,cur)$，其中 $cur$ 就是第一維更新到的位置，$val(l,r)$ 就是區間 $[l,r]$ 中的貢獻，也就是題目所述

查詢的話直接查詢區間最小值即可，現在問題轉換為了，在加入 $a_i$ 后，如何更新線段樹中的信息呢？

感覺本題的難點就是這里了，我思考到這里卡住了，去請教的冰哥，明白了之后就豁然開朗了

因為從前往后加入 $a_i$ 之后，并不會影響 $a_i$ 首次出現的位置，只會影響 $a_i$ 最后一次出現的位置，所以我們記 $last[a_i]$ 為 $a_i$ 最后一次出現的位置，此時就將 $[0,cur]$ 的區間劃分為了兩段：$[0,last[a_i]?1],[last[a_i],cur]$，為什么這樣劃分呢，注意到上面提到的，線段樹中節點維護的信息是：$d{p}_i+val(i+1,cur)$，當此處的 $i$ 取到 $[last[a_i],cur]$ 時，$val(i+1,cur)=0$，即不做貢獻，而取到 $[0,last[a_i]?1]$ 時，$val(i+1,cur)$ 統一增大了 $i?last[a_i]$，所以只需要用線段樹區間更新即可

代碼：

// Problem: E. Partition Game // Contest: Codeforces - Codeforces Round #721 (Div. 2) // URL: https://codeforces.com/contest/1527/problem/E // Memory Limit: 256 MB // Time Limit: 3000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=4e4+100; struct Node {int l,r,mmin,lazy; }tree[N<<2]; int dp[N],a[N],last[N];; void pushup(int k) {tree[k].mmin=min(tree[k<<1].mmin,tree[k<<1|1].mmin); } void pushdown(int k) {if(tree[k].lazy) {int lz=tree[k].lazy;tree[k].lazy=0;tree[k<<1].mmin+=lz;tree[k<<1|1].mmin+=lz;tree[k<<1].lazy+=lz;tree[k<<1|1].lazy+=lz;} } void build(int k,int l,int r) {tree[k]={l,r,inf,0};if(l==r) {tree[k].mmin=dp[l];return;}int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k); } void update(int k,int l,int r,int val) {if(tree[k].l>r||tree[k].r<l) {return;}if(tree[k].l>=l&&tree[k].r<=r) {tree[k].mmin+=val;tree[k].lazy+=val;return;}pushdown(k);update(k<<1,l,r,val);update(k<<1|1,l,r,val);pushup(k); } int query(int k,int l,int r) {if(tree[k].l>r||tree[k].r<l) {return inf;}if(tree[k].l>=l&&tree[k].r<=r) {return tree[k].mmin;}pushdown(k);return min(query(k<<1,l,r),query(k<<1|1,l,r)); } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,k;read(n),read(k);for(int i=1;i<=n;i++) {read(a[i]);}memset(dp,inf,sizeof(dp));dp[0]=0;for(int j=1;j<=k;j++) {build(1,0,n);memset(last,0,sizeof(last));for(int i=1;i<=n;i++) {if(last[a[i]]) {update(1,0,last[a[i]]-1,i-last[a[i]]);}last[a[i]]=i;dp[i]=query(1,0,i-1);}}printf("%d\n",dp[n]);return 0; }

總結

以上是生活随笔為你收集整理的CodeForces - 1527E Partition Game(dp+线段树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。