SWERC 2013 A Mixing Colours

task

小C站在路边等车，无聊之余他玩起了合并方块游戏。
这n个方块排成一排，每个方块有一个颜色，我们会用一个字符串表示。
我们会知道两种颜色可以合并，以及它们合并后的颜色。
现在我们要把这n个方块合并成一个方块，但是问题来了，小C是在烈阳下玩的游戏，屏幕的严重反光让他可能看不清每个方块的颜色，所以他只能用上他强大的第六感来预测。
小C猜了每个方块可能是什么颜色，为颜色k的可能性用浮点数$$cer(k)$$来表示。
他想知道最后最有可能得到的颜色是什么。
$$n,R\le100$$

solution

我们很容易发现此题就是石子合并问题，所以我们同样的用动态规划来写。
但是这题与经典的石子合并不同，多了颜色这一条件，所以我们的dp状态理所应当的需要在多一维。
dp[i][j][k]表示将j~k中的方块合并之后得到颜色i的概率是多少。
那么显然转移方程为：
$$dp[c][l][r]=max(dp[c][l][r],dp[a][l][j]*dp[b][j+1][r])$$
$$dp[c][l][r]=max(dp[c][l][r],dp[b][l][j]*dp[a][j+1][r])$$
其中颜色a与颜色b混合之后得到c，而j∈[l,r)。
这样转移的复杂度就是石子合并的$$n^3$$在加上枚举所有的关系R，最终复杂度为$$O(n^3R)$$
需要注意的是为了防止精度丢失或溢出等问题，我们可以将概率取对数，然后可以把相乘的操作改成相加。

Code

#include <cstdio>
#include <cmath>
#include <string>
#include <map>
#include <iostream>
#include <algorithm>
#define M 305
#define N 505
#define E 105
#define Max(a,b) if(a<(b))a=(b)
using namespace std;
struct kxj{
	int a,b,c;
}s[E];
map<string,int>mp;
string color[M],A,B,C;
int n,m,R,tot;
double dp[M][N][N],cel;
int Id(string str){
	if(mp[str]==0){
		mp[str]=++tot;
		color[tot]=str;
	}
	return mp[str];
}			
int main(){
	bool flag=0;
	while(~scanf("%d",&R)){
		if(flag)puts("");
		else flag=1;
		mp.clear();tot=0;
		for(int i=1;i<=R;i++){
			cin>>A>>B>>C;
			int x=Id(A),y=Id(B),z=Id(C);
			s[i]=(kxj){x,y,z};
		}
		scanf("%d",&m);
		while(m--&&scanf("%d",&n)){
			for(int i=1;i<=n;i++)
				for(int k=1;k<=tot;k++)dp[k][i][i]=-1e99;
			for(int i=1;i<=n;i++){
				while(cin>>A){
					if(A=="END")break;
					scanf("%lf",&cel);
					int x=mp[A];
					dp[x][i][i]=log(cel);
				}
			}
			for(int i=1;i<n;i++){
				for(int l=1,r=l+i;r<=n;l++,r++){
					for(int k=1;k<=tot;k++)dp[k][l][r]=-1e99;
					for(int j=l;j<r;j++){
						for(int k=1;k<=R;k++){
							int a=s[k].a,b=s[k].b,c=s[k].c;
							Max(dp[c][l][r],dp[a][l][j]+dp[b][j+1][r]);
							Max(dp[c][l][r],dp[b][l][j]+dp[a][j+1][r]);
						}
					}
				}
			}
			double mx=-1e99;
			int c=-1;
			for(int i=1;i<=tot;i++){
				if(dp[i][1][n]>mx)mx=dp[i][1][n],c=i;
			}
			if(c==-1)puts("GAMEOVER");
			else cout<<color[c]<<endl;
		}
	}
	return 0;
}