noj 1056 彩色石头 动态规划.txt

包括计算几何、特殊数据结构、组合数学等知识点的代码。每个代码对应一道ACM试题

#include <stdio.h> 
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
//NOj 1056 彩色石头 动态规划
/*
输入：
10 3
2 1 2 2 1 1 3 1 3 3
0 0

输出：
2

提示: 
将第2位置的1,以及倒数第3位置的1拿开即可
*/
#define MAX 9999999
#define NMAX 102
#define KMAX 6
#define KKMAX 34
int wei[KMAX];//分别对应第j种石头情况时，每种石头的取或不取
int f[NMAX][KKMAX];
//f[i][j],前i个石头，当前取了第j种石头情况(0=<j<2^5)所保留的石头数
int d[6]={0,1,2,4,8,16};
int a[NMAX];//输入的每个石头颜色
int b[NMAX][NMAX][KMAX];//b[i][j][k],长度为i，起始点为j的子串所包含颜色k石头的个数

void getwei(int num,int col)
{	//第num种情况，每种石头的取还是不取
	int i=1;
	while(i<=col)
	{
		wei[i]=num%2;
		num/=2;
		i++;
	}
}

void print(int num,int qk)
{
	int i,j;
	cout<<"num="<<num<<"  qk="<<qk<<endl;
	for(i=1;i<=num;i++)
	{
		for(j=0;j<qk;j++)
			cout<<f[i][j]<<" ";
		cout<<endl;
	}
//	system("pause");
}

void printB(int length,int start,int col)
{
	int i,j,k;
	cout<<"length="<<length<<endl;
	for(j=1;j<=col;j++)
	{
		for(k=2;k<=length;k++) cout<<"  ";
		for(i=1;i<=start;i++)
			cout<<b[length][i][j]<<" ";
		cout<<endl;
	}
//	system("pause");
}


void getB(int num,int col)
{
	int i,j,k,jmax;
	memset(b,0,sizeof(b));
	for(j=1;j<=num;j++)
	{
		for(k=1;k<=col;k++)
		{
			if(a[j]==k) b[1][j][k]=1;
			else b[1][j][k]=0;
		}
	}
	for(i=2;i<=num;i++)
	{
		jmax=num-i+1;
		for(j=1;j<=jmax;j++)
		{
			for(k=1;k<=col;k++)
			{	//经典又简单的斜线动态规划，不解释- -
				if(a[j+i-1]==k) b[i][j][k]=b[i-1][j][k]+1;
				else b[i][j][k]=b[i-1][j][k];
			}
		}
//		printB(i,jmax,k);
	}
}
int cal(int num,int col)
{	//重头戏，哈哈
	int i,j,k,max,qk;
	max=0;
	qk=pow(2,col);
	memset(f,0,sizeof(f));
	for(j=0;j<qk;j++)
	{
		getwei(j,col);
		if(wei[a[1]]==0) f[1][j]=0;//第j种情况中，第1个颜色不取
		else f[1][j]=1;//否则，呵呵
	}
	for(i=2;i<=num;i++)
	{
		for(j=1;j<qk;j++)
		{
			getwei(j,col);
			max=f[i-1][j];
			//严重警告：这个if情况不要！！！
			//反例：111222211
			//如果加上这条语句，由于a[9]==a[8],则有f[9][3]=f[8][3]+1,显然错了
			//原因：这时候最佳解的末尾是2而不是1
			//而语句A把这些情况都考虑到了
//			if(a[i]==a[i-1]&&wei[a[i]]==1) max=f[i-1][j]+1;
			for(k=1;k<=i;k++)
			{	//枚举之前字串的最后一个字串的长度
				//语句A
				//思路：把子串分成子串A+子串B+a[i]
				//子串A包含非a[i]颜色，子串B只包含a[i]颜色，每次枚举子串A、B的长度
				if(wei[a[i]]==1&&max<f[i-k][j-d[a[i]]]+b[k][i-k][a[i]]+1)
							max=f[i-k][j-d[a[i]]]+b[k][i-k][a[i]]+1;
			}
			f[i][j]=max;
		}
	}
//	print(num,qk);
	max=0;
	for(j=1;j<=qk;j++)
	{
			if(max<f[num][j]) max=f[num][j];
	}
	return num-max;
}

int main()
{
	int i,num,col;
	scanf("%d%d",&num,&col);
	while(!(0==num&&col==0))
	{
		for(i=1;i<=num;i++)
			scanf("%d",&a[i]);
		getB(num,col);
		cout<<cal(num,col)<<endl;
		scanf("%d%d",&num,&col);
	}
    return 0;
}