首页 > 其他 > 详细

【动态规划】bzoj1939: [Croatian2010] Zuma

时间:2018-10-21 21:20:20      阅读:187      评论:0      收藏:0      [点我收藏+]

隐约记得类似的一道JSOI祖玛……然后好像这题不能够把珠子合并成一段?或许是因为这里珠子碰在一起之后可以不消除?

Description

有一行 N 个弹子,每一个都有一个颜色。每次可以让超过 K 个的连续的同颜色的一段 弹子消失,剩下的会重新紧凑在一起。你有无限的所有颜色的弹子,要求在这行弹子中插入 最少的弹子,使得弹子全部消失。

Input

The first line of input contains two integers N (1 ≤ N ≤ 100) and K (2 ≤ K ≤ 5) - the number of marbles in the initial sequence and the minimal number of consecutive marbles of the same color he could wish to vanish. The next line contains exactly N integers between 1 and 100 (inclusive), separated by one space. Those numbers represent colors of marbles in the sequence Mirko found.

Output

The output should contain only one line with a single integer number - the minimal number of marbles Mirko has to insert to achive the desired effect.

Sample Input

10 4
3 3 3 3 2 3 1 1 1 3

Sample Output

4

题目分析

状态$f[i][j][k]$表示从第$i$个珠子到第$j$个珠子这一段,并在$j$后带有$k$个与$j$同色的珠子情况下的答案。

但实际上不甚明白这样表述状态的充要性。

 1 #include<bits/stdc++.h>
 2 const int maxn = 103;
 3 
 4 int n,m,K,tmp[maxn];
 5 int a[maxn],c[maxn],f[maxn][maxn][maxn];
 6 bool vis[maxn][maxn][maxn];
 7 
 8 int read()
 9 {
10     char ch = getchar();
11     int num = 0;
12     for (; !isdigit(ch); ch=getchar());
13     for (; isdigit(ch); ch=getchar())
14         num = (num<<1)+(num<<3)+ch-48;
15     return num;
16 }
17 inline void Min(int &x, int y){x = x<y?x:y;}
18 int dp(int l, int r, int t)
19 {
20     if (l > r) return 0;
21     if (vis[l][r][t]) return f[l][r][t];
22     vis[l][r][t] = 1;
23     if (a[r]+t >= K) Min(f[l][r][t], dp(l, r-1, 0));
24     else Min(f[l][r][t], dp(l, r, t+1)+1); 
    //这里一开始想成dp(l, r, t-1)+1.实际上这里的状态表示的是逆推。也就是说f[]到完成消除的状态有多远。 
25 for (int k=l; k<r; k++) 26 if (c[k]==c[r]) 27 Min(f[l][r][t], dp(l, k, t+1)+dp(k+1, r-1, 0)); 28 return f[l][r][t]; 29 } 30 int main() 31 { 32 memset(f, 0x3f3f3f, sizeof f); 33 n = read(), K = read(); 34 for (int i=1; i<=n; i++) 35 c[i] = read(), a[i] = 1; 36 printf("%d\n",dp(1, n, 0)); 37 return 0; 38 }

 

 

END

【动态规划】bzoj1939: [Croatian2010] Zuma

原文:https://www.cnblogs.com/antiquality/p/9826650.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!