修改源代码，增加注释。

/* * common.h * * Created on: 2010-2-6 * Author: edan.deng */ #ifndef COMMON_H_ #define COMMON_H_ #include <iostream> #include <vector> #include <map> #include <queue> #include <string> #include <iomanip> using namespace std; #define min(x,y) ((x>y) ? x=y : x) #define max(x,y) ((x>y) ? x : x=y) #define swap(x,y) ((x)^=(y),(y)^=(x),(x)^=(y)) static const int poo=~(1<<31); static const int notdeal=-1; static const int ftest=0; class ACMCommon{ public: int doit(); int timing(); protected: virtual int InsInput()=0; virtual int InsCompute()=0; virtual int InsOutput()=0; }; #endif /* COMMON_H_ */ /* * common.cpp * * Created on: 2010-8-11 * Author: edan.deng */ #include "common.h" int ACMCommon::doit(){ freopen("in.txt", "r", stdin); while(InsInput()){ InsCompute(); InsOutput(); } return 1; } int ACMCommon::timing(){ clock_t start, finish; double ttime; freopen("in.txt", "r", stdin); while(InsInput()){ start = clock(); InsCompute(); InsOutput(); finish = clock(); ttime = (double) (finish - start) / CLOCKS_PER_SEC; cout << " time:" << ttime << endl; } return 1; } //============================================================================ // Name : Astar0602Zuma.cpp // Author : Edan Wade // Version : 0.0 // Copyright : personal // Description : Zuma problem from http://acm.pku.edu.cn/JudgeOnline/problem?id=2915 //============================================================================ #include "../common.h" //class zuma father============================================================================ class zuma: public ACMCommon { protected: //输入一个实例：彩球的信息和消除的参数M。 int InsInput(); //计算一个实例：计算所需最少彩球数量。 int InsCompute(); //输出一个实例：最少彩球的数量。 int InsOutput(); int CutState(int,int,int); int GeneState(); private: int _NumberofBG;//彩球的组数： AAABBBAAA，共三组。BG means BallsGroup. int _M;//连续_M相同的彩球，则可消除。 int _BGColor[200];//第i组彩球的颜色。 int _BGSize[200];//第i组彩球的数量。 int _BGSamecolorIndex[200];//第i组彩球，在同颜色的彩球中的index：AAABBBAAA，第2组AAA在同色的彩球中的index是1。 int _SCIndex2BGIndex[26][100];//_SCIndex2BGIndex[i][j]，颜色为i的所有彩球组中第j组，在所有彩球组中的index。SC means SameColor. private: int _MinBGs[200][200];//_MinBGs[i][j]：消除“第i组彩球与第j间所有彩球(包括i,j组)”所需的最少彩球数。 int _stats[100][2][20][2]; int _NumberofState[100][2]; int _CurColor;//当前加入的彩球组的颜色。 int _IndexI,_IndexJ,_IndexK;//当前加入组，当前计算组，循环组，三组在所有彩球组中的index int _SCIndexI,_SCIndexJ,_SCIndexK;//当前加入组，当前计算组，循环组，三组在所有各自同色彩球组中的index }; int zuma::InsInput(){ //输入：消除参数M，和彩球序列， //转换数据格式，变成计算所需的格式。 //计算：_BGColor[200], _BGSize[200], _BGSamecolorIndex[200], _SCIndex2BGIndex[26][100]. string t_str; int t_num, t_SCIndex2BGIndex[26]; if(!(cin>>t_num>>t_str)) return 0; t_str+=char(64); for(int it_i=0;it_i<26;it_i++) t_SCIndex2BGIndex[it_i]=0; for(int it_i=0;it_i<200;it_i++) _BGColor[it_i]=_BGSize[it_i]=0; int it_j=0; for (int it_i=0, t_BGSize=1; it_i<(int)(t_str.length())-1;it_i++ ){ if(t_str[it_i]==t_str[it_i+1]) t_BGSize++; else{ if(t_BGSize>=t_num) t_BGSize=t_num-1; _BGColor[it_j]=t_str[it_i]-65; _BGSize[it_j]=t_BGSize; _BGSamecolorIndex[it_j]=t_SCIndex2BGIndex[_BGColor[it_j]]; _SCIndex2BGIndex[_BGColor[it_j]][_BGSamecolorIndex[it_j]]=it_j; t_SCIndex2BGIndex[_BGColor[it_j]]++; it_j++;t_BGSize=1; } } _NumberofBG=it_j;_M=t_num; return 1; } int zuma::InsCompute(){ //对一个输入实例，计算其所需最少彩球数。 //初始化 for(int it_i=0;it_i<_NumberofBG;it_i++) _MinBGs[it_i][it_i]=_M-_BGSize[it_i]; //逐一加入_IndexI彩球组，计算“消除_IndexJ(_IndexJ<_IndexI)与_IndexI间所有彩球组”的最少彩球数。 for(_IndexI=1;_IndexI<_NumberofBG;_IndexI++){ //初始化 for(_IndexJ=0;_IndexJ<_IndexI;_IndexJ++)//init minballspair[j][i] _MinBGs[_IndexJ][_IndexI]=_MinBGs[_IndexJ][_IndexI-1]+_MinBGs[_IndexI][_IndexI]; _CurColor=_BGColor[_IndexI]; _SCIndexI=_BGSamecolorIndex[_IndexI]; _stats[_SCIndexI][0][0][0]=_BGSize[_IndexI]; _stats[_SCIndexI][0][0][1]=0; _NumberofState[_SCIndexI][0]=1; _NumberofState[_SCIndexI][1]=0; //计算：消除“_IndexJ与_IndexI间子彩球组”所需最少彩球数，_IndexJ与_IndexI颜色相同。 for(_SCIndexJ=_SCIndexI-1;_SCIndexJ>=0;_SCIndexJ--){ //compute stats[jcolor] _IndexJ=_SCIndex2BGIndex[_CurColor][_SCIndexJ]; _NumberofState[_SCIndexJ][0]=0; _NumberofState[_SCIndexJ][1]=0; //计算 int t_MinBalls=GeneState(); //计算后，更新“_IndexK与_IndexI间子彩球组”所需最少彩球数，_IndexK<_IndexJ for(int it_i=0; it_i<_IndexJ; it_i++) min(_MinBGs[it_i][_IndexI],_MinBGs[it_i][_IndexJ-1]+t_MinBalls); }//end for jcolor j }//end for i return 1; } int zuma::InsOutput(){ cout<<_MinBGs[0][_NumberofBG-1]<<endl; return 1; } int zuma::GeneState(){ //动态规划法：第IndexI组彩球被消除的方式只有两种，单独/合并。 //单独：被注入同色彩球而单独消除，不和其他同色彩球组有关系。 //合并：和其他组同色彩球合并后消除，包括合并后注入新的彩球。 //单独的情况可被看作是只出现过一次的颜色，因此在InsCompute已考虑。 //合并的情况：合并时必有一组在“左”，一组在“右”(可能是已合并过的)； //且“左右”两组的彩球数需小于_M。 //考虑到，本算法从右到左，逐一加入同色彩球组，因此加入过程类似两位_M进制加法运算。 //即“右”组加满了，不能再加了，则加入左组。可用这数表示状态。 //_NumberofState[i][0]：记录第i组彩球的“右”组未满的状态数。 //_NumberofState[i][1]：记录第i组彩球的“右”组已满的状态数。 //_stats[i][0][j][0]：记录第i组彩球的“右”组未满的第j个状态下，“右”组的彩球数； //_stats[i][0][j][1]：记录第i组彩球的“右”组未满的第j个状态下，已消耗的彩球数； //_stats[i][1][j][0]：记录第i组彩球的“右”组已满的第j个状态下，“左”组的彩球数； //_stats[i][1][j][1]：记录第i组彩球的“右”组已满的第j个状态下，已消耗的彩球数； int t_MinBalls=_MinBGs[_IndexJ][_IndexI]; //从_SCIndexI逐一向低位，与_SCIndexI同色的彩球，判断是否合并。直到_SCIndexJ for(_SCIndexK=_SCIndexI; _SCIndexK > _SCIndexJ; _SCIndexK--){ _IndexK=_SCIndex2BGIndex[_CurColor][_SCIndexK]; int t_BGSize=_BGSize[_IndexJ]; int t_Cost; for(int it_i=0; it_i<_NumberofState[_SCIndexK][0]; it_i++){ t_Cost=_MinBGs[_IndexJ+1][_IndexK-1]+_stats[_SCIndexK][0][it_i][1]; if(t_Cost>=t_MinBalls) continue; if(t_BGSize+_stats[_SCIndexK][0][it_i][0]<_M){ CutState(0, t_BGSize+_stats[_SCIndexK][0][it_i][0], t_Cost); min(t_MinBalls, t_Cost+_M-t_BGSize-_stats[_SCIndexK][0][it_i][0]); } else { CutState(1, t_BGSize, t_Cost); min(t_MinBalls, t_Cost); } } for(int it_i=0; it_i<_NumberofState[_SCIndexK][1]; it_i++){ t_Cost=_MinBGs[_IndexJ+1][_IndexK-1]+_stats[_SCIndexK][1][it_i][1]; if(t_Cost>=t_MinBalls) continue; if(t_BGSize+_stats[_SCIndexK][1][it_i][0]<_M){ CutState(1, t_BGSize+_stats[_SCIndexK][1][it_i][0], t_Cost); min(t_MinBalls, t_Cost); } } } _MinBGs[_IndexJ][_IndexI]=t_MinBalls; return _MinBGs[_IndexJ][_IndexI]; } int zuma::CutState(int a_sta, int a_nums, int a_cost){ //剪枝：减去不可能的状态。 int s_badd=1; int t_length=_NumberofState[_SCIndexJ][a_sta]; for(int it_j=0; it_j<t_length;){ if(_stats[_SCIndexJ][a_sta][it_j][0]<a_nums){ if(a_cost-_stats[_SCIndexJ][a_sta][it_j][1] >= a_nums-_stats[_SCIndexJ][a_sta][it_j][0]) { //剪枝：当前状态无需插入 s_badd=0;break; } else it_j++; } else{ if(_stats[_SCIndexJ][a_sta][it_j][1] - a_cost >= _stats[_SCIndexJ][a_sta][it_j][0]-a_nums){ //剪枝：已有状态可以删除 t_length--; _stats[_SCIndexJ][a_sta][it_j][0]=_stats[_SCIndexJ][a_sta][t_length][0]; _stats[_SCIndexJ][a_sta][it_j][1]=_stats[_SCIndexJ][a_sta][t_length][1]; } else it_j++; } } if(s_badd){ _stats[_SCIndexJ][a_sta][t_length][0]=a_nums; _stats[_SCIndexJ][a_sta][t_length][1]=a_cost; t_length++; } _NumberofState[_SCIndexJ][a_sta]=t_length; return 1; }  

/*源代码 及测试例子------------------------------------------------------------------------------------*/

以下源代码都通过了北大ACM网站的测试：http://acm.pku.edu.cn/JudgeOnline/status?user_id=edanwade&problem_id=2915&result=0

zuma2：按照上述思路写的算法。

zuma1：在算法1基础上的优化，简化了状态，增加了剪枝。 

源代码和测试代码已打包上传到CSDN资源，http://download.csdn.net/source/2061939