Halloween Costumes 玄学题

太难了，完全不懂

设\(dp[i][j]\)为第i天到第j天的最少代价

\(dp[i][j]=dp[i][j-1]+1\)(第j天多穿一件衣服)

\(dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j-1])\);(往前找一天k与j衣服相同，把中间的衣服都脱掉)

#include <bits/stdc++.h>

using namespace std;

int n,m,dp[209][209],a[209];

int main()

{

	int t,o=1;

	cin>>t;

	while(t--)

	{

		cin>>n;

	//	memset(dp,20,sizeof(dp));

		for(int i=1;i<=n;i++)	cin>>a[i];

		for(int i=1;i<=n;i++)

			for(int j=i;j<=n;j++)

				dp[i][j]=j-i+1;

		for(int l=2;l<=n;l++)

		{

			for(int i=1;i+l-1<=n;i++)

			{

				int j=i+l-1;

				dp[i][j]=dp[i][j-1]+1;//第j天穿衣服

				//假如第j天不穿，那么要找一个K与第j天的衣服相同

				//然后把k+1到j-1的衣服全部脱掉

				for(int k=i;k<j;k++)

					if(a[k]==a[j])

						dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j-1]);

			}

		}

		cout<<"Case "<<o++<<": ";

		cout<<dp[1][n]<<endl;

	}

}

巴特西

Halloween Costumes 玄学题

最新文章

热门文章