2719834_ac_31ms_148k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#define INF 100000000

int del[101][6][1<<5];
int stone[101];

int Min(int a,int b)
{
	return a>b?b:a;
}

int main()
{
	int i, j, l;
	int m, k, n, ans;

	while (scanf("%d%d",&m,&k)==2&&m&&k)
	{
		for (i = 0; i < m; i++)
			scanf("%d",&stone[i]);
		memset(del,0,sizeof(del));
		for (i = 1; i <= m; i++)
		{
			for (j = 0; j < (1<<k); j++)
			{
				for (l = 0; l < k; l++)
				{
					del[i][l][j] = INF;
				}
			}
		}
		for (i = 1; i <= m; i++)
		{
			for (j = 0; j < (1<<k); j++)
			{
				for (l = 0; l < k; l++)
				{
					if ((1<<l)&j)
					{
						del[i][l][j] = Min(del[i][l][j],del[i-1][l][j]+(stone[i-1]!=l+1));
						for (n = 0; n < k; n++)
						{
							if ((1<<n)&j)
							{
								if(n==l)
									continue;
								del[i][l][j] = Min(del[i][l][j],del[i-1][n][j-(1<<l)]+(stone[i-1]!=l+1));
							}
						}
					}
				}
			}
		}
		ans = INF+1;
		for (i = 0; i < k; i++)
		{
			for (j = 0; j < (1<<k); j++)
			{
				if (del[m][i][j]<ans)
				{
					ans = del[m][i][j];
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}