2016-10-22

ZJU-1206 Win the Bonus

问题描述

原题链接: ZJU 1206

给出 m个长度为3的由 0~9组成的字符串，每个字符串有一个权值，可正可负。

要求构造出一个长度为n的字符串，若字符串中包含题目给出的某个字符串，则获得该字符串的权值。

求一个权值最大的字符串。

输入样例：

输出样例：

算法分析

于 n多达 10 000位，枚举和搜索方法都很容易实现超时。

如果前 k位数字串能够得到最优值，则构成 k+1(k~[3,n])位时肯定也能得到最优值。

所以本题具有最优子结构，可使用动态规划算法求解。

数据结构定义

设银行职员的人数为m，玩家的字符串长度为n

int banker, point; //每个银行职员的数字串及相应的分值

int cost[1000]; //存放银行职员的数字串及相应的分值，数字串的长度为3

//三维数组，opt[l][i][j]表示：当前长度为 l(l~[3-10000])的数字串，第一位数字是 i，第二位数字是 j(i,j~[1-9])的最优值

int opt[10001][10][10];

边界条件

当数字串长度为 1,2时，最优值为0

即opt[l][i][j] = 0; (l=1,2; i,j~[0-9])

递推公式

从右往左dp,只有这样才能保证最后得出的字符串是字典序最小的, ijk组成一个数字串

opt[l][i][j] = max {opt[l-1][j][k] + cost[i100+j10+k]} (k~[3,n], i,j~[0-9])

辅助数组

int path[10001][10][10]; //记录 k值

参考代码

dp算法的实现

void DP(int n) 
{
	int l, i, j, k;
	int max = 0;
	//边界条件 ,只有一个字符和两个字符 
	for(l = 1; l <= 2; l++)
		for(i = 0; i <= 9; i++)
			for(j = 0; j <= 9; j++)
				opt[l][i][j] = 0;
	//递推计算3-n个字符时的最优值 
	for(l = 3; l <= n; l++)
		for(i = 0; i <= 9; i++)
			for(j = 0; j <= 9; j++)
			{
				//长度为 l个字符时，计算由 ijk构成数字串的最优值
				 opt[l][i][j] = -INF;
				 for(k = 0; k <= 9; k++) {
				 	max = opt[l-1][j][k] + cost[i*100+j*10+k];	//从右往左dp
				 	if(max > opt[l][i][j])
				 	{
				 		opt[l][i][j] = max;
				 		path[l][i][j] = k;
				 	}
				 }
			}
}

构造最优解，返回最优值

int traceback(int n)
{
	int i, j;
	int p, q;		//记录最优值对应数字串的第一第二个数字 
	int ans = -INF;	//最优值 
	
	for(i = 0; i <= 9; i++)
		for(j = 0; j <= 9; j++)
		{
			if(opt[n][i][j] > ans)
			{
				ans = opt[n][i][j];
				p = i;
				q = j;
			}
		}
	for(i = n; i >= 3; i--)
	{
		cout << p;
		int k = path[i][p][q];	//找到后一个数字 
		p = q;
		q = k;	
	}	
	//输出最后两位数字
	cout << p << q << endl; 
	return ans;
}

主函数

int main()
{
	freopen("zoj1206.txt", "r", stdin);
	
	int m, n;	// m是银行职员的人数，n是玩家数字串长度 
	int banker, point;
	cin >> m >> n;
	
	int i;
	for(i = 0; i < m; i++) {
		cin >> banker >> point;
		cost[banker] = point;		//将分值存入以银行职员的数字串为下标的元素中 
	}
	//调用dp算法
	DP(n) ;
	//输出最优解
	cout << "获胜字符串为：";
	int ans = traceback(n);
	cout << "最优值为：" << ans << endl; 
	return 0;
}