[BZOJ1151][CTSC2007]动物园zoo 解题报告|DP|位运算

Description

 

 

 

　　最近一直在为了学习算法而做题，这道题是初一小神犇让我看的。感觉挺不错于是写了写。

　　这道题如果是一条线的话我们可以构造一个DP f[i,j]表示以i为起点，i,i+1...i+4的取与不取的状态的二进制为j然后1~i积累的答案

　　以前几乎没有这么写过，因为很难想到j是没有后效性的

　　前一个状态有两种情况，i-1位取，i-1位不取

　　也就是f[i-1,j >> 1] f[i-1,j >> 1+1 << 4]

　　然后小朋友要怎么处理才能做到不重复不遗漏呢

　　答案是记录以每个点为起点，连着5位的状态为j时从那个点出发的小朋友的开心个数

　　显然当我们知道连着5位的状态时，完全可以推出该小朋友开不开心

　　这一部分很容易脑补 但是真正写起来用位运算比较方便

　　而i-1位是否取对当前也是没有影响的，所以这个DP就可以敲起来啦

　　

　　但是如何处理环形？

　　固定前4位的取与不取的状态就可以啦...

　　最后的时间复杂度就是DP状态的O（2^5*C）

　　处理环的代价是O（2^4）

　　最后是O(2^9*C) C<=5*10^5

　　对于10s的时限来说还是可以过哒~

/**************************************************************
    Problem: BZOJ1151
    Author: mjy0724
    Time:3760 ms
    Memory:30336 kb
****************************************************************/

program bzoj1151;
const maxn=100100;
var i,j,x,n,c:longint;
    e,h,l,next,link:array[-1..maxn]of longint;
    hate,love:array[-1..maxn,-1..6]of boolean;
    num,f:array[-1..maxn,-1..32]of longint;

function max(a,b:longint):longint;
begin
    if a>b then exit(a) else exit(b);
end;

procedure solve_num;
var i,j,k,t:longint;
begin
    fillchar(num,sizeof(num),0);
    for i:=1 to n do
        for j:=0 to 31 do
        begin
            k:=link[i];
            while k<>0 do
            begin
                for t:=1 to 5 do if (j and (1 << (5-t)))<>0 then
                //这个位运算刚开始一直出错，不能写成=1因为and之后虽然只有1位是1但是不一定在最后一位QAQ
                begin
                    if love[k,t] then
                    begin
                        inc(num[i,j]);break;//这里的break很重要 因为1个小朋友只能算一次
                    end;
                end else
                begin
                    if hate[k,t] then
                    begin
                        inc(num[i,j]);break;
                    end;
                end;
                k:=next[k];
            end;
        end;
end;

procedure dp;
var head,i,j,tot,k,ans:longint;
begin
    ans:=0;
    for head:=0 to 15 do//枚举前4位的状态
    begin
        fillchar(f,sizeof(f),192);
        fillchar(f[0],sizeof(f[0]),0);
        for i:=1 to 4 do
            for j:=(head << i) and 31 to (head << i) and 31+1 << i-1 do //and 31是小小的位运算技巧，把前面的头都去掉啦
                f[i,j]:=max(f[i-1,j >> 1],f[i-1,j >> 1+1 << 4])+num[i,j];

        for i:=5 to n-4 do
            for j:=0 to 31 do
                f[i,j]:=max(f[i-1,j >> 1],f[i-1,j >> 1+1 << 4])+num[i,j];
        tot:=0;
        for i:=n-3 to n do
        begin
            inc(tot);
            for k:=0 to 1 << (5-tot)-1 do
            begin
                j:=k << tot+head >> (n-i);
                f[i,j]:=max(f[i-1,j >> 1],f[i-1,j >> 1+1 << 4])+num[i,j];
            end;
        end;

        for i:=0 to 31 do ans:=max(ans,f[n,i]);
    end;
    writeln(ans);
end;

begin
    readln(n,c);
    fillchar(hate,sizeof(hate),false);
    fillchar(love,sizeof(love),false);
        for i:=1 to c do
    begin
        read(e[i],h[i],l[i]);
        for j:=1 to h[i] do
        begin
            read(x);
                if x>=e[i] then hate[i,x-e[i]+1]:=true else hate[i,(x+n-e[i]) mod n+1]:=true;//这里处理环的情况 表示第i个小朋友视野里的第几个是否讨厌
        end;
        for j:=1 to l[i] do
        begin
            read(x);
                if x>=e[i] then love[i,x-e[i]+1]:=true else love[i,(x+n-e[i]) mod n+1]:=true;
        end;
        readln;
            next[i]:=link[e[i]];link[e[i]]:=i;
    end;
       solve_num;
       dp;
end.