- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
-
一个正整数数列，可以将它切割成若干个数据段，每个数据段由值相同的相邻元素构成。该数列的神奇之处在于，每次切除一个数据段后，
该数据段前后的元素自动连接在一起成为邻居。例如从数列“2 8 9 7 7 6 9 4”中切除数据段“7 7 ”后，余下的元素会构成数列“2 8 9 6 9 4”
请问若要将该数列切割成若干个数据段，则至少会切出来几个数据段？样例： 按下列顺序切割数列“2 8 9 7 7 6 9 4”，只要切割成 6段
切割出“7 7”，余下 “2 8 9 6 9 4”
切割出 “6”，余下 “2 8 9 9 4”
切割出 “9 9”，余下 “2 8 4”
切割出 “2”，余下 “8 4”
切割出 “8”，余下 “4” - 输入
- 第一行是一个整数，示共有多少组测试数据。每组测试数据的输入包括两行：第一行是整数N, N<=200,表示数列的长度，第二行是N个正整数。
- 输出
- 每个测试案例的输出占一行，是一个整数。格式是：
Case n: x
n是测试数据组编号，x是答案 - 样例输入
-
2 8 2 8 9 7 7 6 9 4 16 2 8 9 7 7 6 9 4 4 2 8 4 2 7 6 9
- 样例输出
-
Case 1: 6 Case 2: 11
1 #include<iostream> 2 #include<queue> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 int a[202]; 7 int dp[202][202]; //从i到j需要的最小消除次数 8 int main(){ 9 int t; 10 cin>>t; 11 for(int tmp = 1; tmp <= t; tmp++){ 12 int n, i, len, k; 13 cin>>n; 14 memset(a, 0, sizeof(a)); 15 memset(dp,0,sizeof(dp)); 16 for(i = 1; i <= n; i++) 17 cin>>a[i]; 18 for(i = 1; i <= n; i++) 19 for(int j = i; j <= n; j++) 20 dp[i][j] = 1<<20; 21 for(i = 1; i <= n; i++){ 22 dp[i][i] = 1; 23 } 24 /* 25 for(i = 1; i < n; i++){ 26 if(a[i]==a[i+1]) dp[i][i+1] = 1; 27 else dp[i][i+1] = 2; 28 }*/ 29 for(len = 2; len <= n; len++){ 30 for(i = 1; i+len-1<= n; i++){ 31 int j = i+len-1; 32 for(k = i; k < j; k++){ 33 //2 8 9 7 9 6 9 34 if(a[k]==a[j]){ 35 dp[i][j] = min(dp[i][k]+dp[k+1][j-1], dp[i][j]); 36 } 37 else dp[i][j] = min(dp[i][k]+dp[k+1][j], dp[i][j]); 38 } 39 } 40 } 41 cout<<"Case "<<tmp<<": "<<dp[1][n]<<endl; 42 } 43 return 0; 44 }
备注：区间dp是有模板的，就像这样先枚举长度是常规操作。。
我真的不明白为什么这道题的动态转移方程为啥是这样。这都是咋想出来的啊。
x老师管这类题叫区间消消乐。我没完全看懂他写的那一整套套路，但我感觉就这道题好像可以解释了：
找a[k]==a[j]这个点是通用的套路，找到之后，先把（k+1,j-1)消掉，也就是后半段除了最后一个数，然后把a[j]留着和(i,k)一起消，这道题里没有什么乱七八糟的分值之类的设定，所以a[j]和前面（i,k)一起消的开销依然为dp[i][k]。所以动态转移方程是这样。
我觉得我看懂了。配合着blocks这道题理解就很容易了。
C. 删除数组
对于这种区间消消乐的题目，有2个套路：
1. 初始可以直接对原数组进行unique操作，即让所有重复段len=1
N = unique(s+1,s+1+N) - (s+1);
2. O(N^4) 区间DP
dp[l][r][len] = "消去[l,r]这段，以及l之前一段长度=len的且都=s[l]的相同元素"
a. len和s[l]直接一起消去：dp[l][r][len] = f(len+1) + dp[l+1][r][len], f()是1个和消去长度相关的函数
b. 找到(L,R]中某个s[i]==s[l]，先消去[L+1,i-1]这段：dp[l][r][len] = dp[l+1][i-1][0] + dp[i][r][len+1]
这样可以应对大部分类似题目
本题中，f()恒等于1，所以unique之后可以直接去掉第三维，用dfs式DP解决，复杂度O(N^3)要求常数很小
int memo[MAXN][MAXN];//初始memo[i][i]=1，其他=0
int dfs(int l, int r){
if(memo[l][r]) return memo[l][r];
LL ans = 1 + dfs(l+1,r);
if(s[r]==s[l]) ans = min(ans, 1 + dfs(l+1,r-1));
for(int i=l+1;i<r;i++){
if(s[l]==s[i]) ans = min(ans, dfs(l+1,i-1) + dfs(i,r));
}
return memo[l][r] = ans;
}
Ans = dfs(1,N,0)
对于blocks这道题，就完美符合这个套路。
而对于我们这道简易版的题呢，len维度直接去掉就可以了，因为没有计分环节（能合并的话立即合并后消除总是最优的）。dp[l][r][len] = f(len+1) + dp[l+1][r][len]就是dp[l][r][len] = 1+ dp[l+1][r][len]，和第二种情况可以合并，只要枚举k是从l到r-1就可以了。
好了！我明白了！