1596：動物園

時間限制: 1000 ms ??? ??? 內存限制: 524288 KB

【題目描述】

原題來自：APIO 2007

新建的圓形動物園是亞太地區的驕傲。圓形動物園坐落于太平洋的一個小島上，包含一大圈圍欄，每個圍欄里有一種動物。如下圖所示：

你是動物園的公關主管。你要做的是，讓每個參觀動物園的游客都盡可能高興。今天有一群小朋友來到動物園參觀，你希望能讓他們在動物園度過一段美好的時光。但這并不是一件容易的事——有些小朋友喜歡某些動物，而有些小朋友則害怕某些動物。例如， Alex 喜歡可愛的猴子和考拉，而害怕擁有鋒利牙齒的獅子。而 Polly 會因獅子有美麗的鬃毛而喜歡它，但害怕有臭味的考拉。

你可以選擇將一些動物從圍欄中移走以使得小朋友不會害怕。但你移走的動物也不能太多，否則留給小朋友們觀賞的動物就所剩無幾了。

每個小朋友站在大圍欄圈的外面，可以看到連續的?5?個圍欄。你得到了所有小朋友喜歡和害怕的動物信息。當下面兩處情況之一發生時，小朋友就會高興：

1、至少有一個他害怕的動物被移走；

2、至少有一個他喜歡的動物沒被移走。

例如，考慮下圖中的小朋友和動物：

假如你將圍欄?4?和?12?的動物移走。Alex 和 Ka-Shu 將很高興，因為至少有一個他們害怕的動物被移走了。這也會使 Chaitanya 高興，因為他喜歡的圍欄?6?和?8?中的動物都保留了。但是，Polly 和 Hwan 將不高興，因為他們看不到任何他們喜歡的動物，而他們害怕的動物都還在。這種安排方式使得三個小朋友高興。

現在換一種方法，如果你將圍欄?4?和?6?中的動物移走，Alex 和 Polly 將很高興，因為他們害怕的動物被移走了。Chaitanya 也會高興，雖然他喜歡的動物?6?被移走了，他仍可以看到圍欄?8?里面他喜歡的動物。同樣的 Hwan 也會因可以看到自己喜歡的動物?12?而高興。唯一不高興的只有 Ka-Shu。

如果你只移走圍欄?13?中的動物，Ka-Shu 將高興，因為有一個他害怕的動物被移走了，Alex, Polly, Chaitanya 和 Hwan 也會高興，因為他們都可以看到至少一個他們喜歡的動物。所以有?5?個小朋友會高興。這種方法使得了最多的小朋友高興。

【輸入】

輸入的第一行包含兩個整數?N,C，用空格分隔。N?是圍欄數，C?是小朋友的個數。圍欄按照順時針的方向編號為?1,2,3,…,N。

接下來的?C?行，每行描述一個小朋友的信息，以下面的形式給出：E?F?L?X1?X2??XF?Y1?Y2??YL。

其中E?表示這個小朋友可以看到的第一個圍欄的編號，換句話說，該小朋友可以看到的圍欄為?E,E+1,E+2,E+3,E+4。注意，如果編號超過?N?將繼續從?1?開始算。如：當?N=14,E=13時，這個小朋友可以看到的圍欄為?13,14,1,213,14,1,2?和?33。

F?表示該小朋友害怕的動物數。L?表示該小朋友喜歡的動物數。

圍欄?X1,X2,?,XF?中包含該小朋友害怕的動物。圍欄?Y1,Y2,?,YL中包含該小朋友喜歡的動物。

X1,X2,?,XF,Y1,Y2,?,YL?是兩兩不同的整數，而且所表示的圍欄都是該小朋友可以看到的。

【輸出】

僅輸出一個數，表示最多可以讓多少個小朋友高興。

小朋友已經按照他們可以看到的第一個圍欄的編號從小到大的順序排好了（這樣最小的E?對應的小朋友排在第一個，最大的?E?對應的小朋友排在最后一個）。

注意可能有多于一個小朋友對應的?E?是相同的。

【輸入樣例】

14 5 2 1 2 4 2 6 3 1 1 6 4 6 1 2 9 6 8 8 1 1 9 12 12 3 0 12 13 2

【輸出樣例】

5

【提示】

樣例說明 1

樣例?1?給出了前面描述的示例情形。它使得所有小朋友（C=5）高興。

樣例輸入 2

12 7 1 1 1 1 5 5 1 1 5 7 5 0 3 5 7 9 7 1 1 7 9 9 1 1 9 11 9 3 0 9 11 1 11 1 1 11 1

樣例輸出 2

6

樣例說明 2

樣例?2?給出了這樣的情形，要使得所有小朋友（C=7）都高興是不可能的。

數據范圍與提示：

對于每一個測試點，如果你的答案正確，則該測試點得滿分，否則得?00?分。

對于全部數據，10≤N≤10⁴,1≤C≤5×10⁴,1≤E≤N。

?

sol：首先由題解可知這是一道狀壓dp好題。

令dp[i][j]表示以i為開頭的5個動物以狀態為j時最多能讓多少小朋友快樂（需要在每個小朋友的位置E上預處理出使E,E+1,~，E+5狀態為j時的快樂人數），然后先暴力枚舉(n-3~n的狀態)之后n*32轉移就可以了

#include <bits/stdc++.h> using namespace std; typedef int ll; inline ll read() {ll s=0;bool f=0;char ch=' ';while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch^48);ch=getchar();}return (f)?(-s):(s); } #define R(x) x=read() inline void write(ll x) {if(x<0){putchar('-');x=-x;}if(x<10){putchar(x+'0');return;}write(x/10);putchar((x%10)+'0');return; } inline void writeln(ll x) {write(x);putchar('\n');return; } #define W(x) write(x),putchar(' ') #define Wl(x) writeln(x) const int N=10005,B=35,inf=0x3f3f3f3f; int n,C,Gongx[N][B],dp[N][B]; int main() {int i,j,k;R(n); R(C);for(i=1;i<=C;i++){int Haip=0,Xih=0,E,F,L;R(E); R(F); R(L);for(j=1;j<=F;j++){int x=read();Haip|=(1<<((x-E+n)%n));}for(j=1;j<=L;j++){int x=read();Xih|=(1<<((x-E+n)%n));}for(j=0;j<32;j++){Gongx[E][j]+=(((j^31)&Haip)||(Xih&j))?1:0;}}int ans=0;for(i=0;i<16;i++){for(j=0;j<32;j++) dp[0][j]=-inf;dp[0][i<<1]=dp[0][(i<<1)|1]=0;for(j=1;j<=n;j++){for(k=0;k<32;k++){dp[j][k]=max(dp[j-1][(k&15)<<1],dp[j-1][((k&15)<<1)|1])+Gongx[j][k];}}ans=max(ans,max(dp[n][i<<1],dp[n][(i<<1)|1]));}Wl(ans);return 0; } /* input 14 5 2 1 2 4 2 6 3 1 1 6 4 6 1 2 9 6 8 8 1 1 9 12 12 3 0 12 13 2 output 5input 12 7 1 1 1 1 5 5 1 1 5 7 5 0 3 5 7 9 7 1 1 7 9 9 1 1 9 11 9 3 0 9 11 1 11 1 1 11 1 output 6 */ View Code

轉載于:https://www.cnblogs.com/gaojunonly1/p/10371782.html

總結

以上是生活随笔為你收集整理的一本通1596动物园的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。