BZOJ 3925 지진 후의 환상의 고장

17268 단어 DPDP 최적화기대하다.
제목은 우리가 방향을 바꾸어 통계할 수 있다. 앞에서 k의 작은 변을 일일이 열거하면 그림이 연결되고 k의 작은 변을 빼면 그림이 연결되지 않는다. 그러면 공헌을 할 수 있다.그러면: a n s = ∑ k = 1 m E (k) k m + 1 ans =\sum{k=1}^{m}E(k)\rack{m+1}ans=k=1∑mE(k)m+1k 그 중에서 E(k)E(k)E(k)는 전 k변으로 그림을 연결하고 전 k-1변으로 그림을 연결하지 않습니다.a n s = ∑ k = 1 m E ( k ) ∗ ∑ i = 1 k 1 m + 1 ans =\frac {\sum_{k=1}^{m} E(k) *\sum_{i=1}^k1}{m+1} ans=m+1∑k=1m​E(k)∗∑i=1k​1​ a n s = ∑ k = 1 m ∑ i = k m E ( i ) m + 1 ans =\frac{\sum_{k=1}^{m}\sum_{i=k}^m E(i) }{m+1} ans=m+1∑k=1m​∑i=km​E(i)​ ∑ i = k m E ( i )\sum_{i=k}^mE(i)∑i=kmE(i)의 값은 E[전k-3변은 그림을 연결할 수 없다] E[전k-1변은 그림을 연결할 수 없다] E[전k-1변은 그림을 연결할 수 없다] E[전k-1변은 그림을 연결할 수 없다] 이것으로 전환상 압DP를 보충할 수 있다.
AC Code: 
#include
#define maxn 11
#define maxm 55
using namespace std;

int n,m;
int sz[1<<maxn],lg[1<<maxn];
double C[maxm][maxm],f[maxm][1<<maxn][2];
int c[maxn][maxn];

int main()
{
	scanf("%d%d",&n,&m);
	C[0][0] = 1;
	for(int i=1;i<maxm;i++)
	{
		C[i][0] = 1;
		for(int j=1;j<=i;j++)
			C[i][j] = C[i-1][j-1] + C[i-1][j];
	}
	for(int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),u--,v--,c[u][v]=c[v][u]=1;
	for(int i=0;i<n;i++) lg[1<<i] = i;
	for(int i=1;i<(1<<n);i++)
	{
		int tmp = i & (-i) , v = lg[i & (-i)],rsta=i-tmp;
		sz[i] = sz[rsta];
		for(int j=0;j<n;j++)
			if((rsta)>>j&1)
				sz[i] += c[j][v];
	}
	for(int sta=1;sta<(1<<n);sta++)
	{
		for(int i=0;i<=sz[sta];i++)
		{
			int p = sta & (-sta);
			for(int t=sta;t;t=(t-1)&(sta))
				if((t&p) && (t!=sta))
				{
					for(int k=0;k<=i;k++)
						f[i][sta][0] += f[k][t][1] * C[sz[sta-t]][i-k];
				}
			f[i][sta][1] = C[sz[sta]][i] - f[i][sta][0];
		}
	}
	
	double ans = 0;
	for(int i=0;i<=m;i++) 
		ans += f[i][(1<<n)-1][0] / C[m][i];
	ans /= m+1;
	printf("%.6lf
",ans);
}
jquery에서 쿠키 정보 얻기, 하루에 한 번만 튀기
1부터 시작된 iOS 팀 개발: 애플 Developer Program에 멤버 초대

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage