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