萌新求助qwq

P3622 [APIO2007] 动物园

foxdemon @ 2019-11-01 10:00:50

rt,第54行的初始化是为了什么啊...

#include<bits/stdc++.h>
using namespace std ;

const int MAX = 100 ;
const int maxx = 31 ;//2^5 - 1
const int N = 50005 ;
int dp[N][MAX] ;
int n , m ;
int num[N][MAX] ;
int ans ;

int main()
{

    cin >> n >> m ;
    for ( int i = 1 ; i <= m ; i++ )    
    {
        int begin , f , l , t , fear = 0 , love = 0 ;
        cin >> begin >> f >> l ;

        for ( int j = 1 ; j <= f ; j++ )
        {
            cin >> t ;
            t = ( t + n - begin ) % n ;//害怕的动物在目前能看到的第几个(0 1 2 3 4) 
            fear = fear|(1<<t) ;//把害怕的动物转化为二进制数
            //1:害怕   2:不害怕 
            //例:2 3 4 5 6 中3 6害怕,则二进制数为 10010  (注:方向相反)
        }

        for ( int j = 1 ; j <= l ; j++ )
        {
            cin >> t ;
            t = ( t + n - begin ) % n ;//喜欢的动物在能看到的第几个(0 1 2 3 4) 
            love = love|(1<<t) ;//把喜欢的动物转化为二进制
            //1:喜欢   2:不喜欢 
            //例:2 3 4 5 6 中2 4喜欢,则二进制数为 00101 (方向相反)
        }

        for ( int j = 0 ; j <= maxx ; j++ )//枚举每种状态(每一位都有两种选择:0表示笼子不移开,1表示移开,所以状态为0~2^n-1) 
        {
            if ( ( (j&fear) || (~j&love) ) )
            //j&fear:如果说在j这个状态下,有害怕的笼子被移开了
            //例:2 3 4 5 6中4害怕,二进制数为0 0 1 0 0,若状态j为1 0 1 0 1(这里的0,1表示是否移走),那么此时害怕的笼子被移开了,那么这个孩子就会高兴 
            //~j&love:如果说在j这个状态下,喜欢的笼子没有被移开
            //例:2 3 4 5 6 中4害怕,二进制数为0 0 1 0 0, 若状态j为1 0 1 0 1,则~j为0 1 0 1 0,此时喜欢的笼子没有被移走,那么这个孩子会高兴 
            {
                num[begin][j]++ ;//以begin为起点、状态为j时高兴的孩子数 
            }
        }
    }

    for ( int i = 0 ; i <= maxx ; i++ )
    {
        memset(dp[0],128,sizeof(dp[0])) ;
        dp[0][i] = 0 ;//没有编号为0的笼子 
        for ( int j = 1 ; j <= n ; j++ )
        {
            for ( int k = 0 ; k <= maxx ; k++ )
            {
                dp[j][k] = max ( dp[j - 1][ (k&15)<<1 ] , dp[j - 1][ (k&15)<<1|1 ] ) + num[j][k]  ;
            }
        }
        if ( ans < dp[n][i] )
        {
            ans = dp[n][i] ;
        }
    }
    cout << ans << endl ;
    //system("pause");

    return 0 ;

}

by jiangXxin @ 2019-11-01 10:51:06

去你的萌新


by foxdemon @ 2019-11-01 11:10:02

@a2954898606 qnd qndmx


|