Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

考察位运算和DP

Posted by 13408100238 at 2014-07-28 16:11:25 on Problem 3071
#include"iostream"
#include"cstdio"
#include"cstring"
using namespace std;
const int ms=130;
double p[ms][ms];
double dp[ms][8];
int main()
{
	int n,i,j;
	while(scanf("%d",&n),n!=-1)
	{
		int m=(1<<n);
		for(i=0;i<m;i++)
		{
			for(j=0;j<m;j++)
				scanf("%lf",&p[i][j]);
			dp[i][0]=1;
		}
		int ans;
		for(i=0;i<n;i++)
		{
			ans=0;
			for(j=0;j<m;j++)
			{
				double sum=0;
				for(int k=(1<<i);k<(1<<(i+1));k++)
				{
					sum+=dp[k^j][i]*p[j][k^j];
				}
				dp[j][i+1]=dp[j][i]*sum;
				if(dp[j][i+1]>dp[ans][i+1])
					ans=j;
			}
		}
		printf("%d\n",ans+1);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator