@hdu - 5009@ Paint Pearls

矫情吗；* 2023-06-01 13:59 21阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

给定一个长度为 n 的序列，每一个位置有一个目标颜色，初始所有位置都没有颜色。  
每次操作可以选择一个区间，将这个区间内的位置的颜色改为其**目标颜色**，代价是区间内不同的目标颜色数量^2。  
求将所有位置改为目标颜色的最小代价。

**Input**  
多组数据。  
每组数据第一行一个整数 n(1 ≤ n ≤ 5×10^4)，表示序列长度。  
第二行包含 a1,a2,...,an (1 ≤ ai ≤ 10^9 ) 表示每个位置的目标颜色。

**Output**  
对于每组数据，输出最小代价。

**Sample Input**  
3  
1 3 3  
10  
3 4 2 4 4 2 4 3 2 2  
**Sample Output**  
2  
7

## @solution@ ##

不难想到区间不能相交，于是就有一个 O(n^2) 的 dp：dp\[i\] 表示考虑前 i 位的最小代价，有 dp\[i\] = min\{dp\[j\] + val(j+1, i)\}。

考虑优化。  
看到代价是平方好像可以斜率，不过仔细一想这个斜率会发生诡异的变化，不行。  
其他优化行不通时考虑决策单调性，好像也不怎么单调。  
其实很简单，没有那么多套路。

考虑 ans 的一个上界是 n：将所有颜色一个位置一个位置的改变。  
如果区间内的颜色个数 > \\(\\sqrt\{n\}\\)，则代价显然比 ans 的上界还要大，故不合法。于是每一个区间的颜色个数不能超过 \\(\\sqrt\{n\}\\)。

假如以 i 为区间右端点，如果 j 这个位置的颜色在区间 \[j+1, i\] 出现过，则决策 \[j, i\] 不会比决策 \[j+1, i\] 更差。  
这意味着有效的决策点其实只跟每种颜色在 \[1, i\] 中最后一次出现的位置有关，所以决策点数量只跟区间内所含不同颜色个数有关。

又因为上面每一个区间的颜色个数不能超过 \\(\\sqrt\{n\}\\)，所以有效决策点的数量也不超过 \\(\\sqrt\{n\}\\)。  
用链表维护一下有效决策点即可，时间复杂度 \\(O(n\\sqrt\{n\})\\)。

## @accepted code@ ##

#include<map> #include<cmath> #include<cstdio> #include<algorithm> using namespace std; const int MAXN = 50000; map<int, int>mp; int lst[MAXN + 5], nxt[MAXN + 5]; void link(int x, int y) { nxt[x] = y, lst[y] = x; } void erase(int x) { nxt[lst[x]] = nxt[x]; lst[nxt[x]] = lst[x]; } int a[MAXN + 5], dp[MAXN + 5]; void solve(int n) { for(int i=1;i<=n;i++) scanf("%d", &a[i]), lst[i] = nxt[i] = -1; mp.clear(); lst[0] = nxt[0] = -1; int sq = sqrt(n); for(int i=1;i<=n;i++) { link(i - 1, i); if( mp.count(a[i]) ) erase(mp[a[i]]); mp[a[i]] = i, dp[i] = n; for(int j=1,p=i;j*j<=n&&p;j++,p=lst[p]) dp[i] = min(dp[i], dp[lst[p]] + j*j); } printf("%d\n", dp[n]); } int main() { int n; while( scanf("%d", &n) == 1 ) solve(n); }

## @details@ ##

话说这个题看到平方真的很容易往斜率优化那边靠。。。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11307205.html