状态压缩dp---zoj_3502

      http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3502

      题目大意就是要做n道题目，顺序不定，每一题的AC概率和之前做过的题目有关，给出一张概率表。最后要求给出一个字典排序最小的

题目序列使得AC题目的数量的期望最大。

      n道题一共有2^n种状态，dp[i]表示第i中状态下的最大期望。假设i=10111那么dp[i]如何更新呢,显然dp[i]和dp[j]有关,其中

j=00111,10011,10101,10110,dp[j]的状态分别加上第5,3,2,1道题所对应的期望值就是dp[i]所对应的所有状态，取最大的一种更新即可。

      这道题还要注意的就是浮点数的比较大小的问题。当dp[i]-q和0比较时，应该设一个精度误差EPS，然后比较：

      dp[i]-q=0对应fabs(dp[i]-q)<EPS

      dp[i]-q>0对应dp[i]-q>EPS

      dp[i]-q<0对应dp[i]-q<EPS

代码如下：

    

#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
const double EPS=1e-8;
const int MAXN=12;
double p[MAXN][MAXN];
double dp[1<<MAXN];
string pre[1<<MAXN];
int n,cases;
double q;
int main()
{
	freopen("e:\\zoj\\zoj_3502.txt","r",stdin);
	cin>>cases;
	while(cases--)
	{
		cin>>n;
		for(int i=0;i<n;++i)
		for(int j=0;j<n;++j)
			scanf("%lf",&p[i][j]);
		dp[0]=0;
		pre[0]="";
		for(int k=1;k<(1<<n);++k)
		{
			dp[k]=-1;
			for(int i=0;i<n;++i)
			{
				if(k&(1<<i))
				{
					q=0;
					for(int j=0;j<n;++j)
					{
						if(k&(1<<j))
						{
							q=max(q,p[j][i]);
						}	
					}
					q=dp[k^(1<<i)]+q/100;
					if((q>dp[k]+EPS)||(q>dp[k]-EPS&&pre[k^(1<<i)]<=pre[k]))
					{
						dp[k]=q;
						pre[k]=pre[k^(1<<i)];
						pre[k]+=('A'+i);
					}		
				}	
			}	
		}
		printf("%.2f\n%s\n", dp[(1 << n) - 1], pre[(1 << n) - 1].c_str());
		//printf("%.2lf\n",dp[(1<<n)-1]);
		//cout<<pre[(1<<n)-1]<<endl;	
	}	

	return 0;
}