求助简单DP题90pts求助
查看原帖
求助简单DP题90pts求助
376137
Lazy_Labs楼主2022/5/1 12:59
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
#define dbout cerr<<"[DeBug]:"
#define mem(x,y) memset(x,y,sizeof(x))
inline int read()
{
 	int x(0),f(1);char c=getchar();
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-48,c=getchar();
	return f*x;
}
double xxx[1100][1100];
double dp[1100][2];
int main()
{
	//fr(rnfmabj);
	int n=read(),x=1<<n;
	for(int i=0;i<x;i++)
	for(int j=0;j<x;j++)
	xxx[i][j]=(double)read()/100;
	for(int i=0;i<x;i++)dp[i][1]=dp[i][0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<x;j++)
		{
			double xx=0;
			int l=(j/(1<<i))*(1<<i),r=(j/(1<<i)+1)*(1<<i);
			if(j>=l+(1<<(i-1)))r-=(1<<(i-1));else l+=(1<<(i-1));
			for(int k=l;k<r;k++)
			xx+=xxx[j][k]*dp[k][(i&1)^1];
			dp[j][i&1]=dp[j][(i&1)^1]*xx;
		}
	}
	int add=0;
	for(int i=1;i<x;i++)if(dp[add][(n&1)^1]+0.00000000001<dp[i][(n&1)^1])add=i;
	printf("%d",add+1);
	return 0;
}
2022/5/1 12:59
加载中...