首页 > 其他分享 >CF 1527 E

CF 1527 E

时间:2024-09-17 18:51:00浏览次数:8  
标签:int 复杂度 tr CF 1527 代价 dp

题目描述

我们定义一个数组 \(P\) 的代价为:

\[\sum \limits_{x\in P} last(x)-first(x) \]

这里 \(first(x),last(x)\) 是指 \(x\) 第一次,最后一次出现的位置。

你需要将数组 \(A\) 分成恰好 \(k\) 段,求最小总代价。

思路

令 \(dp_{i,j}\) 表示已经分了 \(i\) 段,末尾在 \(j\)​ 的最小代价。

由于代价是最后一个减前一个,可以看作是 \(i_2-i_1+i_3-i_2+\dots\),这里 \(i_j\) 表示第 \(j\) 个 \(x\) 的下标。

所以转移可以这样来实现:当枚举到 \(i\) 时,之后 \(a\rightarrow b(1\le a<last,i\le b\le N)\) 的转移一定会多 \(i-last\) 的代价。这个可以用线段树维护区间最小值。

每次做完一轮 dp 就把 \(dp\) 值丢进线段树即可。

空间复杂度 \(O(N)\),时间复杂度 \(O(NK\log N)\)。

代码

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 35005;

struct Segment_Tree {
  int l[MAXN << 2], r[MAXN << 2], Min[MAXN << 2], lazy[MAXN << 2];
  void build(int u, int s, int t) {
    l[u] = s, r[u] = t, lazy[u] = 0;
    if(s == t) {
      Min[u] = 0;
      return;
    }
    int mid = (s + t) >> 1;
    build(u << 1, s, mid), build((u << 1) | 1, mid + 1, t);
    Min[u] = min(Min[u << 1], Min[(u << 1) | 1]);
  }
  void tag(int u, int x) {
    Min[u] += x, lazy[u] += x;
  }
  void pushdown(int u) {
    tag(u << 1, lazy[u]), tag((u << 1) | 1, lazy[u]), lazy[u] = 0;
  }
  void update(int u, int s, int t, int x) {
    if(s > t) {
      return;
    }
    if(l[u] >= s && r[u] <= t) {
      tag(u, x);
      return;
    }
    pushdown(u);
    if(s <= r[u << 1]) {
      update(u << 1, s, t, x);
    }
    if(t >= l[(u << 1) | 1]) {
      update((u << 1) | 1, s, t, x);
    }
    Min[u] = min(Min[u << 1], Min[(u << 1) | 1]);
  }
  int Getmin(int u, int s, int t) {
    if(s > t) {
      return 0;
    }
    if(l[u] >= s && r[u] <= t) {
      return Min[u];
    }
    pushdown(u);
    int x = int(2e9);
    if(s <= r[u << 1]) {
      x = min(x, Getmin(u << 1, s, t));
    }
    if(t >= l[(u << 1) | 1]) {
      x = min(x, Getmin((u << 1) | 1, s, t));
    }
    return x;
  }
}tr;

int n, k, a[MAXN], last[MAXN], dp[MAXN];

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> k;
  for(int i = 2; i <= n + 1; ++i) {
    cin >> a[i];
  }
  tr.build(1, 1, n + 1);
  tr.update(1, 2, n + 1, int(2e9));
  for(int i = 1; i <= k; ++i) {
    for(int j = 1; j <= n; ++j) {
      last[j] = 1;
    }
    for(int j = 2; j <= n + 1; ++j) {
      tr.update(1, 1, last[a[j]] - 1, j - last[a[j]]);
      last[a[j]] = j;
      dp[j] = tr.Getmin(1, 1, j - 1);
    }
    tr.build(1, 1, n + 1);
    tr.update(1, 1, 1, int(2e9));
    for(int j = 2; j <= n + 1; ++j) {
      tr.update(1, j, j, dp[j]);
    }
  }
  cout << dp[n + 1];
  return 0;
}

标签:int,复杂度,tr,CF,1527,代价,dp
From: https://www.cnblogs.com/yaosicheng124/p/18417386

相关文章

  • 「杂题乱刷2」CF1527B2
    题目链接CF1527B1(luogu)CF1527B2(luogu)CF1527B1(codeforces)CF1527B2(codeforces)解题思路这篇题解分B1,B2两个部分来讲。B1sol:考虑字符串中\(0\)的数量,设这个值为\(sum\):若\(sum\equiv0\pmod{2}\),且字符串回文时,那么此时,后手可以一直模仿先手的操作,直到字符串含有......
  • 201909-2 小明种苹果(续)ccfcsp
    一道简单的模拟。。。includeincludeusingnamespacestd;intmain(){constintN=1010;booldrop[N]={false};intn,m,i,j,cnt=0,cnt1=0;cin>>n;inty;intsum=0,sum1,temp=0;intindex;for(i=0;i<n;i++){ sum1=0;scanf("%d",&m);for(j=0;j&......
  • 题解 CF993E 【Nikita and Order Statistics】
    初看这道题,以为又是什么数据结构数数题,没啥思路,结果推式子时搞出了一个类似可以卷积的玩意儿,所以果断\(FFT\)解决。那我们来分析问题:这道题里,值域没用,每一个数只要管它与\(x\)的相对大小关系即可。如果它小于\(x\)那么有贡献,赋值为一,否则为零。然后,可以求前缀和,区间部分......
  • CF 1839 D
    题目描述给定\(N\)个不同颜色的小球。你可以进行以下操作:插入一个颜色为\(0\)的小球,此操作最多执行\(k\)次。选择一个非零球,使得该球与至少一个\(0\)小球相邻。并把该小球移动到任意位置。这样会花费\(1\)的代价。对于每个\(1\lek\leN\)求出将序列变成一个去......
  • CF1334F Strange Function 题解
    传送门定义一个函数\(f\),输入一个数组\(a\),输出一个数组\(b\)为\(a\)的子序列:\(b_1=a_1\),设\(b_i\)在\(a\)中的位置为\(pos_i\),则\(b_i\)为\(a_{pos_{i-1}+1}\sima_n\)中第一个严格大于\(b_{i-1}\)的数。\(n\le5\times10^5\),\(|p_i|\le10^9,1\lea_i,b_i\le......
  • 201412-2 Z字形扫描 ccf
    先找到斜线的起始点然后输出斜线上各点include<bits\stdc++.h>typedeflonglongll;usingnamespacestd;intmain(){intn,i,j,sum,cnt,x,y;cin>>n;inta[501][501];intb[1000][2];for(i=0;i<n;i++){for(j=0;j<n;j++)scanf("%d",&a[i][j]);}......
  • 202312-2 因子化简ccfcsp
    常规质数因子带相关资料抄写稍加修改指数的筛选部分includeinclude<math.h>typedeflonglongll;usingnamespacestd;boolisprime(lln){inti;if(n<=1)returnfalse;intsq=(int)sqrt(1.0n);for(i=2;i<=sq;i++){if(n%i==0)returnfalse;}returntrue;}cons......
  • CF 1801 C
    题目描述有\(N\)个专辑,第\(i\)个专辑中有\(k_i\)首歌曲,其中第\(j\)首歌的酷炫程度为\(a_{i,j}\)。你会选择一个排列\(p_1,p_2,\dots,p_N\),每次你会将\(p_i\)中所有歌曲从前往后依次听完。每当你遇到一个严格大于之前听过所有歌曲的歌曲,则你会对这个歌曲产生印象。......
  • CF1039D You Are Given a Tree
    CF1039DYouAreGivenaTree咋其他题解都带根号?根号是坏文明,这里是俩\(\log\)做法,能够跑到\(300\)ms以内。首先考虑暴力贪心,从叶子向根合并,可以取出一条链的时候就取出来,否则就连一条尽可能长的链往上合并。具体的设\(f_{x,i}\)为当\(k=i\)时,在\(x\)处能取出的最......
  • CF1793E Velepin and Marketi
    首先发现,每个人过的题是不同的,所以我们不关心过了那些题目。我们要直接去求分成\(k\)组最多的通过数是不容易的。我们可以转换一下,求当\(i\)个题通过的时候__最多__分多少组。为什么记最多,因为化成\(k\)个组通过\(i\)题可以的情况下,我们可以任意合并两个组,保证依然可以......