首页 > 其他分享 >CF 1839 D

CF 1839 D

时间:2024-09-16 22:14:10浏览次数:10  
标签:le int 1839 小球 CF MAXN ans dp

题目描述

给定 \(N\) 个不同颜色的小球。你可以进行以下操作:

  • 插入一个颜色为 \(0\) 的小球,此操作最多执行 \(k\) 次。
  • 选择一个非零球,使得该球与至少一个 \(0\) 小球相邻。并把该小球移动到任意位置。这样会花费 \(1\) 的代价。

对于每个 \(1\le k \le N\) 求出将序列变成一个去除 \(0\) 后升序的序列所需最小代价。

思路

定义 \(dp_{i,j}\) 表示把 \([1,i]\) 排序,使用 \(j\) 个 \(0\) 小球所需的最小代价。

如果 \(a_i > a_{i-1}\),那么我们有转移 \(dp_{i,j}\leftarrow dp_{i-1,j}\)。

否则,对于所有 \(0\le k < i-1且a_k<a_i\),那么我们有 \(dp_{i,j}\leftarrow dp_{k,j-1}+i-k-1\),因为此时使用了一个 \(0\) 球,并且除端点外区间中每个点都需要移动一次。

空间复杂度 \(O(N^2)\),时间复杂度 \(O(N^3)\)。

代码

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

const int MAXN = 505, INF = MAXN;

int t, n, a[MAXN], dp[MAXN][MAXN], ans;

void Solve() {
  cin >> n;
  for(int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for(int i = 0; i <= n + 1; ++i) {
    for(int j = 0; j <= n; ++j) {
      dp[i][j] = INF;
    }
  }
  dp[0][0] = 0, a[n + 1] = n + 1;
  for(int i = 1; i <= n + 1; ++i) {
    for(int j = 0; j <= n; ++j) {
      if(a[i] > a[i - 1]) {
        dp[i][j] = dp[i - 1][j];
      }
      if(j) {
        for(int k = 0; k < i - 1; ++k) {
          if(a[k] < a[i]) {
            dp[i][j] = min(dp[i][j], dp[k][j - 1] + i - k - 1);
          }
        }
      }
    }
  }
  ans = dp[n + 1][0];
  for(int i = 1; i <= n; ++i) {
    ans = min(ans, dp[n + 1][i]);
    cout << ans << " \n"[i == n];
  }
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  for(cin >> t; t--; Solve()) {
  }
  return 0;
}

标签:le,int,1839,小球,CF,MAXN,ans,dp
From: https://www.cnblogs.com/yaosicheng124/p/18416688

相关文章

  • 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\)题可以的情况下,我们可以任意合并两个组,保证依然可以......
  • [题解]CF542A Place Your Ad Here
    思路首先因为电视台比广告多一个信息,所以通常来说枚举电视台是更有前途的。因此枚举每一个电视台,考虑所有广告的贡献。对于一个电视台,\(c_i\)是定值,也就是找到所有广告与电视台所表示区间交得最多的那一个。假设枚举的电视台控制了\([L,R]\)区间,则广告\([l,r]\)会有三种方......
  • CF1187E sol
    首先不难发现,确定了根以后答案是固定的。设\(sz_i\)表示以1为根的树中,以1为根的子树大小;\(f_i\)表示以1为根的树中,以\(i\)为根的子树得到的最大权值,可以得到转移\[f_u=sz_u+\sum_{v\inson_u}f_v\]然后设\(g_v\)表示先选\(v\)的最大权值,\(v\)的父亲为\(......
  • CF605E
    题解总之,赞美太阳#include<bits/stdc++.h>usingnamespacestd;inlineintread(){ charc;intf=1,res=0; while(c=getchar(),!isdigit(c))if(c=='-')f*=-1; while(isdigit(c))res=res*10+c-'0',c=getchar(); returnres*f;}constintN=1e3+5......
  • 掌握CFML:在输出缓冲区中高效搜索字符串的技巧
    掌握CFML:在输出缓冲区中高效搜索字符串的技巧在开发过程中,特别是使用ColdFusionMarkupLanguage(CFML)进行Web开发时,处理大量数据并快速找到特定字符串是一项常见且重要的任务。为了提高程序效率,我们经常需要在输出缓冲区中搜索特定的字符串,并在必要时对其进行处理。本文将分......