UVA12283题解

Jason12 · 2022-05-01 20:40:03 · 题解

题目：

传送门

思路：

区间 dp，用 s_{i,j} 表示第 i 到第 j 次派对至少需要的衣服数，则结果为 s_{i,j} 若第 i 次和第 j 次需要的衣服种类相同，则可以使用相同的衣服，第 i+1 次到第 j-1 次派对所需要的衣服可以穿在第 i 次和第 j 次派对的衣服外面，用好后脱下，那么到第 j 次派对时，穿在最外面的就是第 i 次派对穿的那件衣服了，所以要穿的衣服数和第 i 次派对到第 j-1 次派对相等，状态转移方程为：

若第 i 次和第 j次派对要穿的衣服不同，则要穿的衣服数和第 i 次到第 j-1 次要穿的衣服数 +1 相等，状态转移方程为：

用 for 循环来枚举中间点 k，状态转移方程为：

需要注意输出格式里每行有两个空格。（详见代码）

代码：

#include <bits/stdc++.h>
  using namespace std;
int t,n,m,a[105],s[105][105],i,j,k,l,o;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);//两行输入输出加速。 
    cin>>t;
    for (l=1;l<=t;l++)
    {
        cin>>n>>m;
        for (i=1;i<=n;i++)
        {
            cin>>a[i];
            s[i][i]=1;//一次派对只用一件衣服。 
        }
        for (o=2;o<=n;o++)//枚举 i 和 j 之间的距离。 
        {
            for (i=1,j=i+o-1;j<=n;i++,j=i+o-1)
            {
                if (a[i]==a[j]) s[i][j]=s[i][j-1];//当第 i 次和第 j 次派对需要的衣服相同。 
                else s[i][j]=s[i][j-1]+1;//不同 
                for (k=i;k<j;k++)//枚举中间点。 
                {
                    s[i][j]=min(s[i][j],s[i][k]+s[k+1][j]);
                }
            }
        }
        cout<<"Case "<<l<<": "<<s[1][n]<<endl;//注意输出格式 
    }
    return 0;
}