Hackers'Crackdown(UVA UVA 11825 U압dp)
6803 단어 rack
분석: n개의 집합을 최대한 여러 조로 나누어 각 조의 집합(컴퓨터 i 및 인접한 컴퓨터의 집합)을 전집으로 집합시켰다. 이 문제를 통해 상태 s의 각 집합이 합쳐졌는지 여부를 배웠다. dp[s]상태 s는 파괴할 수 있는 가장 많은 서비스이고 dp[s]=max(dp[s], dp[s^ss]+1)(ss는 s의 서브집합이며 표시된 집합은 전집합이다).
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <complex>
#include <cassert>
#include <utility>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
#define lson l,m,rt<<1
#define pi acos(-1.0)
#define rson m+1,r,rt<<11
#define All 1,N,1
#define read freopen("in.txt", "r", stdin)
#define N 1<<17
const ll INFll = 0x3f3f3f3f3f3f3f3fLL;
const int INF= 0x7ffffff;
const int mod = 1000000007;
int dp[N],c[N],cover[N],n;
int solve(){
int cas=(1<<n)-1;
for(int s=0;s<=cas;++s){
cover[s]=0;
for(int i=0;i<n;++i)
if(s&(1<<i))
cover[s]|=c[i];//
}
dp[0]=0;
for(int s=1;s<=cas;++s){
dp[s]=0;
for(int i=s;i;i=((i-1)&s))// s
if(cover[i]==cas)
dp[s]=max(dp[s],dp[s^i]+1);
}
return dp[cas];
}
int main()
{
int num=0;
while(~scanf("%d",&n)){
if(n==0)break;
int a;
for(int i=0;i<n;++i){
c[i]=(1<<i);
scanf("%d",&a);
int x;
while(a--){
scanf("%d",&x);
c[i]|=(1<<x);//
}
}
printf("Case %d: %d
",++num,solve());
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.