해커의 공격 Hacker's crackdown UVA11825 상태 압축 동적 계획

제목은 n대의 서버가 n류 프로그램을 실행하고 있다는 뜻이다. 한 해커는 n중류의 바이러스를 가지고 있다. 최대 한 대의 서버에 바이러스를 넣을 수 있지만 인접한 서버는 같은 종류의 바이러스에 감염될 수 있다. 한 개의 서비스만 정지하고 정지할 수 있는 프로그램의 최대 종류를 묻는다.
해결 방법은 위치로 집합을 표시하고 문제의 답안은 가장 많은 집합을 구하는 조합에 해당하며 조합 내의 집합과 집합은 전집합이다.이 조합의 가장 큰 수를 구하시오.전이 방정식 f[s]={f[s^s0],s0 이런 조합 내의 집합과 집합은 전집합}+1이다.
여기에는 다음과 같은 컬렉션 작업이 포함됩니다.
또는 연산하여 원소를 집합에 넣는다.
매거 집합의 모든 조합의 가능성:

for(int i=0;i<(1<<n);i++)
{
    for(int j=0;j<n;j++)
   {
        if(i&(1<<n))cover[i]=cover[i]|s[j];
    }
}

매거 집합 s의 모든 서브집합

for(int i=s;i>0;i=(i-1)&s)
{
    //insert code
}

코드:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 1<<17
int cover[MAXN];
int s[20];
int f[MAXN];
int main()
{
	int n;
	int kas=0;
	while(scanf("%d",&n),n)
	{
		memset(s,0,sizeof(s));
		for(int i=0;i<n;i++)
		{
			int m;cin>>m;
			s[i]=s[i]|(1<<i);
			for(int j=0;j<m;j++)
			{
				int t;cin>>t;
				s[i]=s[i]|(1<<t);
			}
		}
		memset(cover,0,sizeof(cover));
		for(int i=0;i<(1<<n);i++)
		{
                       for(int j=0;j<n;j++)
		       {
			       if(i&(1<<j))cover[i]=cover[i]|s[j];
		       }
		}
		memset(f,0,sizeof(f));
		for(int i=0;i<(1<<n);i++)
		{
			for(int j=i;j>0;j=(j-1)&i)
			{
				if(cover[j]==(1<<n)-1)
				{
					f[i]=max(f[i],f[i^j]+1);
				}
			}
		}
		printf("Case %d: %d
",++kas,f[(1<<n)-1]);
	}
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

omniauth-twitter가 무엇을하고 있는지 보았습니다.

의 트위터 버전. 거의 omniauth-facebook 때와 같은 내용이 되어 버렸으므로, ↑를 읽은 분은 스루 해 OK라고 생각합니다. omniauth (1.2.2) omniauth-oauth2 (1.0.1) om...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

해커의 공격 Hacker's crackdown UVA11825 상태 압축 동적 계획

좋은 웹페이지 즐겨찾기