考察:区间dp
区间dp的题想重写一遍,tm学了和没学一样,前几天都在睡,根本没刷题TAT
思路:
本道题要想到由局部最优解推导整体最优解,为什么能推到呢?首先f[i][j]表示[i,j]区间内要穿衣服的最少数量,在[i,j]区间内,枚举断点,由更小的最优解得到[i,j]区间的最优解.如果存在断点,那么一定可以枚举求出,如果不存在,说明答案是连续的.f[i][j] = f[i][j-1]这里只考虑区间内的最优解,j后面不考虑.
和这道题很像的涂色洛谷P4170,也不能说很像吧,简直就是一模一样
a[i]==a[j]与不等于不是对立关系,f[l][r]是要在两个选择里取最优解
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 using namespace std;
6 const int N = 110;
7 int a[N],f[N][N];
8 int main()
9 {
10 int T,kcase = 0;
11 scanf("%d",&T);
12 while(T--)
13 {
14 int n;
15 scanf("%d",&n);
16 for(int i=1;i<=n;i++) scanf("%d",&a[i]) ;
17 for(int i=1;i<=n;i++) f[i][i] = 1;
18 for(int len=2;len<=n;len++)
19 for(int l=1;l+len-1<=n;l++)
20 {
21 int r = l+len-1; f[l][r] = 0x3f3f3f3f;
22 if(a[l]==a[r]) f[l][r] = min(f[l][r-1],f[l][r]);
23 for(int k=l;k<r;k++)
24 f[l][r] = min(f[l][k]+f[k+1][r],f[l][r]);
25 }
26 printf("Case %d: %d\n",++kcase,f[1][n]);
27 }
28 return 0;
29 }