E - Partition Game

題目描述

定義一個序列 $t$ 的 $cost$ 為 $cost(t)={\sum }_{x\in set(t)}last(x)?first(x)$ 。

其中 $set(t)$ 為 $t$ 中所有元素組成的不重集合， $last(x)$ 表示元素 $x$ 出現的最后一個位置， $first(x)$ 表示元素 $x$ 出現的第一個位置。

給定序列 $a$ ，把 $a$ 分成恰好 $k$ 段，求每一段的 $cost$ 值相加的和最小是多少。

數據范圍與提示

$1\le n\le 35000，1\le k\le \min (n,100)，1\le a_i\le n$ 。

思路

這題沒什么性質，就是一個純的數據結構優化 $\text{DP}$ 的題。

設 $dp[i][j]$ 表示前 $i$ 個數劃分成 $j$ 段時這 $j$ 段的 $cost$ 相加的最小值，顯然有
$$dp[i][j]=\min (dp[k][j?1]+cost(a[k+1,i]))，k\in [0,i?1]$$
其中 $a[i,j]$ 表示序列 $a$ 中第 $i$ 個元素到第 $j$ 個元素組成的子段。

我們可以對于每個 $j$ ，用一棵線段樹維護 $dp[k][j]+cost(a[k+1,i])$ 的最小值，由于 $last(x)?first(x)$ 就等于每相鄰兩個 $x$ 的距離相加，所以每次只需要把新出現的一對相鄰 $x$ 加進對應的 $cost$ 里面即可。

具體地，設 $bf(i)$ 表示 $i$ 左邊第一個與它相同的元素的位置，那么我們需要利用數據結構把每一個 $dp[k][j]+cost(a[k+1,i])，k\in [0,bf[i]?1]$ 都加上 $i?bf[i]$ 。

時間復雜度 $O(nk\log n)$ ，你可能需要一些常數比較小的數據結構 （比如zkw） 。

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<stack> #include<map> #define ll long long #define MAXN 35005 #define uns unsigned //#define int ll using namespace std; inline ll read(){ll x=0;bool f=1;char s=getchar();while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+s-'0',s=getchar();return f?x:-x; } int n,k,a[MAXN],bf[MAXN],las[MAXN],p; ll f[105][MAXN*3],lz[105][MAXN*3],dp[MAXN][105]; inline void add(int K,int l,int r,ll ad){for(l=p+l-1,r=p+r+1;l^1^r;){if(~l&1)f[K][l^1]+=ad,lz[K][l^1]+=ad;if(r&1)f[K][r^1]+=ad,lz[K][r^1]+=ad;l>>=1,r>>=1;f[K][l]=min(f[K][l<<1],f[K][l<<1|1])+lz[K][l];f[K][r]=min(f[K][r<<1],f[K][r<<1|1])+lz[K][r];}for(l>>=1;l;l>>=1)f[K][l]=min(f[K][l<<1],f[K][l<<1|1])+lz[K][l]; } inline void change(int K,int x,ll d){for(f[K][p+x]=d,x=(p+x)>>1;x;x>>=1)f[K][x]=min(f[K][x<<1],f[K][x<<1|1])+lz[K][x]; } signed main() {n=read(),k=read();for(int i=1;i<=n;i++)a[i]=read();for(int i=1;i<=n;i++)bf[i]=las[a[i]],las[a[i]]=i;for(p=1;p<n+3;p<<=1);memset(f,0x3f,sizeof(f));change(0,1,0);for(int i=1;i<=n;i++){if(bf[i]>0)for(int j=0;j<=k;j++)add(j,1,bf[i],i-bf[i]);for(int j=1;j<=min(i,k);j++)dp[i][j]=f[j-1][1],change(j,i+1,dp[i][j]);}printf("%lld\n",dp[n][k]);return 0; }

總結

以上是生活随笔為你收集整理的CF1527E Partition Game——DP优化的全部內容，希望文章能夠幫你解決所遇到的問題。

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