程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva 11825 Hackers' Crackdown (狀壓dp,子集枚舉)

uva 11825 Hackers' Crackdown (狀壓dp,子集枚舉)

編輯:C++入門知識

題目鏈接:uva 11825


題意:

你是一個黑客,侵入了n台計算機(每台計算機有相同的n種服務),對每台計算機,你可以選擇終止一項服務,則他與其相鄰的這項服務都終止。你的目標是讓更多的服務癱瘓(沒有計算機有該項服務)。


思路:(見大白70頁,我的方程與大白不同)

把n個集合P1、P2、Pn分成盡量多的組,使得每組中所有集合的並集等於全集,這裡的集合Pi是計算機i及其相鄰計算機的集合,用cover[i]表示若干Pi的集合S中所有集合的並集,dp[s]表示子集s最多可以分成多少組,則

如果cover[s]=all,那麼dp[s]至少為1.

dp[s]=max(dp[s],dp[s0]+dp[s^s0]); (兩個子集的和)


代碼:

#include 
#include 
#include 
#define N 16
using namespace std;

int n, m, x, dp[1<


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved