SRM 463 Div1 Medium Nisoku

という訳で昨日の全探索パターンを書いてみた。
そう、状態数は2500しかないんだよね。

カードのs枚目からt枚目までの最適解をmemo[s][t]とすると、
memo[s][t]=min{memo[s+1][t-1]+opt(Cs,Ct),
min{opt(memo[s][i],memo[i+1][t])|s≦i＜t}
}
ただしopt(a,b)はa+b,a*bの大きいほう。

class Nisoku {
	public:
	double memo[60][60];
	int n;
	vector<double> C;
	
	double theMax(vector <double> cards)
	{
		sort(all(cards));
		C=cards;n=C.size();
		
		rep(i,n)rep(j,n)memo[i][j]=-1;
		return dfs(0,n-1);
	}
	
	double dfs(int s,int t)
	{
		if(memo[s][t]>=0)return memo[s][t];
		if(s>t)return 0;
		if(s==t)return C[s];
		
		double a=max(C[s]+C[t],C[s]*C[t]);
		double b=dfs(s+1,t-1);
		double ret=max(a*b,a+b);
		
		for(int i=s;i<t;i++)
		{
			double a=dfs(s,i),b=dfs(i+1,t);
			ret=max(ret,max(a+b,a*b));
		}
		return memo[s][t]=ret;
	}
}

（ヘッダ、マクロは省略）

大きいケースでも5msくらいで余裕で終わたorz