【HDU】5208 Where is Bob 【DP】
7679 단어 HDU
제목 분석:
상태를 dp[cur][l1][r1][l2][r2]로 설정하면cur는 현재 2진법의 위치를 나타내고 l1은 첫 번째 사람의 수의 하계를 나타내며 r1은 첫 번째 사람의 수의 상계를 나타내고 l2는 두 번째 사람의 수의 하계를 나타내며 r2는 두 번째 사람의 수의 상계를 나타낸다.l1,r1,l2,r2는 모두 01 변수이다. 첫 번째 수에 대해 하계가 끼어 있으면 시간 l1을 0으로 할 수 없고, 그렇지 않으면 l1을 1로 하면 작아질 수 있다.첫 번째 수의 r1, 그리고 두 번째 수의 l2, r2는 같은 이치이다.
그리고 우리 dp는 숫자의 높은 위치에서 시작하여 어떤 사람이 마지막에 1로 변할 수 있다면 우선적으로 1로 변한다. 왜냐하면 뒤에 있는 모든 1을 합치면 이 1보다 작기 때문이다.그리고 우리는 모든 상황에 대해 판단한다.자신이 어떻게 선택해야 하는지, 그리고 상대방을 어떻게 겨냥해야 하는지, 상황에 따라 가장 큰 값을 뽑아야 하는지를 토론한다.이렇게 해서 마지막으로 dp[최고위][0][0][0][0]가 답이다.
PS: 이 블로그는 내가 AC라는 문제를 토로하기 위해 쓴 것이다!무려 130여줄의if,else=.너무 멍청해서 모든 상황을 일일이 토론할 수밖에 없다.
my code:
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>
#include <math.h>
#include <string>
#include <vector>
using namespace std;
typedef long long LL ;
#define rep( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i )
#define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )
const int MAXN = 31 ;
int dp[MAXN][2][2][2][2] ;
int vis[MAXN][2][2][2][2] ;
int L1 , R1 , L2 , R2 ;
int dfs ( int cur , int l1 , int r1 , int l2 , int r2 ) {
if ( cur == -1 ) return 0 ;
if ( vis[cur][l1][r1][l2][r2] ) return dp[cur][l1][r1][l2][r2] ;
vis[cur][l1][r1][l2][r2] = 1 ;
int ans = 0 , t = 1 << cur ;
int a = L1 >> cur & 1 ;
int b = R1 >> cur & 1 ;
int c = L2 >> cur & 1 ;
int d = R2 >> cur & 1 ;
if ( !l1 && !r1 ) {
if ( !l2 && !r2 ) {
if ( a == b ) {
if ( c == d ) {
if ( a == c ) ans = dfs ( cur - 1 , 0 , 0 , 0 , 0 ) ;//ok
else ans = t + dfs ( cur - 1 , 0 , 0 , 0 , 0 ) ;//ok
} else {//c = 0 , d = 1
if ( a == 0 ) ans = dfs ( cur - 1 , 0 , 0 , 0 , 1 ) ;//ok
else ans = dfs ( cur - 1 , 0 , 0 , 1 , 0 ) ;//ok
}
} else {//a = 0 , b = 1
if ( c == d ) {
if ( c == 0 ) ans = t + dfs ( cur - 1 , 1 , 0 , 0 , 0 ) ;//ok
else ans = t + dfs ( cur - 1 , 0 , 1 , 0 , 0 ) ;//ok
} else {
ans = max ( dfs ( cur - 1 , 0 , 1 , 0 , 1 ) , dfs ( cur - 1 , 1 , 0 , 1 , 0 ) ) ;//ok
}
}
} else if ( l2 && !r2 ) {
if ( a == b ) {
if ( a == 1 ) {
if ( d == 1 ) ans = dfs ( cur - 1 , 0 , 0 , 1 , 0 ) ;//ok
else ans = t + dfs ( cur - 1 , 0 , 0 , 1 , 0 ) ;//ok
} else {
if ( d == 1 ) ans = dfs ( cur - 1 , 0 , 0 , 1 , 1 ) ;//ok
else ans = dfs ( cur - 1 , 0 , 0 , 1 , 0 ) ;//ok
}
} else {//a = 0 , b = 1
if ( d == 1 ) ans = max ( dfs ( cur - 1 , 0 , 1 , 1 , 1 ) , dfs ( cur - 1 , 1 , 0 , 1 , 0 ) ) ;//ok
else ans = t + dfs ( cur - 1 , 1 , 0 , 1 , 0 ) ;//ok
}
} else if ( !l2 && r2 ) {
if ( a == b ) {
if ( a == 0 ) {
if ( c == 0 ) ans = dfs ( cur - 1 , 0 , 0 , 0 , 1 ) ;//ok
else ans = t + dfs ( cur - 1 , 0 , 0 , 0 , 1 ) ;//ok
} else {//a = 1
if ( c == 0 ) ans = dfs ( cur - 1 , 0 , 0 , 1 , 1 ) ;//ok
else ans = dfs ( cur - 1 , 0 , 0 , 0 , 1 ) ;//ok
}
} else {//a = 0 , b = 1
if ( c == 0 ) ans = max ( dfs ( cur - 1 , 0 , 1 , 0 , 1 ) , dfs ( cur - 1 , 1 , 0 , 1 , 1 ) ) ;//ok
else ans = t + dfs ( cur - 1 , 0 , 1 , 0 , 1 ) ;//ok
}
} else if ( l2 && r2 ) {
if ( a == b ) ans = dfs ( cur - 1 , 0 , 0 , 1 , 1 ) ;//ok
else ans = max ( dfs ( cur - 1 , 1 , 0 , 1 , 1 ) , dfs ( cur - 1 , 0 , 1 , 1 , 1 ) ) ;//ok
}
} else if ( l1 && !r1 ) {
if ( !l2 && !r2 ) {
if ( c == d ) {
if ( c == 1 ) {
if ( b == 1 ) ans = t + dfs ( cur - 1 , 1 , 1 , 0 , 0 ) ;//ok
else ans = t + dfs ( cur - 1 , 1 , 0 , 0 , 0 ) ;//ok
} else {//c = 0
if ( b == 1 ) ans = t + dfs ( cur - 1 , 1 , 0 , 0 , 0 ) ;//ok
else ans = dfs ( cur - 1 , 1 , 0 , 0 , 0 ) ;//ok
}
} else {
if ( b == 1 ) ans = max ( dfs ( cur - 1 , 1 , 1 , 0 , 1 ) , dfs ( cur - 1 , 1 , 0 , 1 , 0 ) ) ;//ok
else ans = dfs ( cur - 1 , 1 , 0 , 0 , 1 ) ;//ok
}
} else if ( l2 && !r2 ) {
if ( d == 1 ) {
if ( b == 1 ) ans = max ( dfs ( cur - 1 , 1 , 1 , 1 , 1 ) , dfs ( cur - 1 , 1 , 0 , 1 , 0 ) ) ;//ok
else ans = dfs ( cur - 1 , 1 , 0 , 1 , 1 ) ;//here!!!!!!!!!!!!!!!!!! before ac , final one is zero
} else {
if ( b == 1 ) ans = max ( dfs ( cur - 1 , 1 , 1 , 1 , 0 ) , t + dfs ( cur - 1 , 1 , 0 , 1 , 0 ) ) ;
else ans = dfs ( cur - 1 , 1 , 0 , 1 , 0 ) ;
}
} else if ( !l2 && r2 ) {
if ( c == 0 ) {
if ( b == 1 ) ans = max ( dfs ( cur - 1 , 1 , 1 , 0 , 1 ) , dfs ( cur - 1 , 1 , 0 , 1 , 1 ) ) ;
else ans = dfs ( cur - 1 , 1 , 0 , 0 , 1 ) ;
} else {
if ( b == 1 ) ans = max ( t + dfs ( cur - 1 , 1 , 1 , 0 , 1 ) , dfs ( cur - 1 , 1 , 0 , 0 , 1 ) ) ;
else ans = t + dfs ( cur - 1 , 1 , 0 , 0 , 1 ) ;
}
} else if ( l2 && r2 ) {
if ( b == 1 ) ans = max ( dfs ( cur - 1 , 1 , 1 , 1 , 1 ) , dfs ( cur - 1 , 1 , 0 , 1 , 1 ) ) ;//ok
else ans = dfs ( cur - 1 , 1 , 0 , 1 , 1 ) ;//ok
}
} else if ( !l1 && r1 ) {
if ( !l2 && !r2 ) {
if ( c == d ) {
if ( c == 1 ) {
if ( a == 0 ) ans = t + dfs ( cur - 1 , 0 , 1 , 0 , 0 ) ;
else ans = dfs ( cur - 1 , 0 , 1 , 0 , 0 ) ;
} else {
if ( a == 0 ) ans = t + dfs ( cur - 1 , 1 , 1 , 0 , 0 ) ;
else ans = t + dfs ( cur - 1 , 0 , 1 , 0 , 0 ) ;
}
} else {
if ( a == 0 ) ans = max ( dfs ( cur - 1 , 0 , 1 , 0 , 1 ) , dfs ( cur - 1 , 1 , 1 , 1 , 0 ) ) ;
else ans = dfs ( cur - 1 , 0 , 1 , 1 , 0 ) ;
}
} else if ( l2 && !r2 ) {
if ( d == 1 ) {
if ( a == 0 ) ans = max ( dfs ( cur - 1 , 0 , 1 , 1 , 1 ) , dfs ( cur - 1 , 1 , 1 , 1 , 0 ) ) ;
else ans = dfs ( cur - 1 , 0 , 1 , 1 , 0 ) ;
} else {
if ( a == 0 ) ans = t + dfs ( cur - 1 , 0 , 1 , 1 , 0 ) ;
else ans = t + dfs ( cur - 1 , 0 , 1 , 1 , 0 ) ;
}
} else if ( !l2 && r2 ) {
if ( c == 0 ) {
if ( a == 0 ) ans = max ( dfs ( cur - 1 , 1 , 1 , 1 , 1 ) , dfs ( cur - 1 , 0 , 1 , 0 , 1 ) ) ;
else ans = dfs ( cur - 1 , 0 , 1 , 1 , 1 ) ;
} else {
if ( a == 0 ) ans = t + dfs ( cur - 1 , 0 , 1 , 0 , 1 ) ;
else ans = dfs ( cur - 1 , 0 , 1 , 0 , 1 ) ;
}
} else if ( l2 && r2 ) {
if ( a == 0 ) ans = max ( dfs ( cur - 1 , 0 , 1 , 1 , 1 ) , dfs ( cur - 1 , 1 , 1 , 1 , 1 ) ) ;//ok
else ans = dfs ( cur - 1 , 0 , 1 , 1 , 1 ) ;//ok
}
} else if ( l1 && r1 ) {
if ( !l2 && !r2 ) {
if ( c == d ) ans = t + dfs ( cur - 1 , 1 , 1 , 0 , 0 ) ;
else ans = max ( dfs ( cur - 1 , 1 , 1 , 0 , 1 ) , dfs ( cur - 1 , 1 , 1 , 1 , 0 ) ) ;
} else if ( l2 && !r2 ) {
if ( d == 1 ) ans = max ( dfs ( cur - 1 , 1 , 1 , 1 , 0 ) , dfs ( cur - 1 , 1 , 1 , 1 , 1 ) ) ;
else ans = t + dfs ( cur - 1 , 1 , 1 , 1 , 0 ) ;
} else if ( !l2 && r2 ) {
if ( c == 0 ) ans = max ( dfs ( cur - 1 , 1 , 1 , 0 , 1 ) , dfs ( cur - 1 , 1 , 1 , 1 , 1 ) ) ;
else ans = t + dfs ( cur - 1 , 1 , 1 , 0 , 1 ) ;
} else if ( l2 && r2 ) {
ans = dfs ( cur - 1 , 1 , 1 , 1 , 1 ) ;//ok , ans = 0
}
}
//printf ( "dp[%d][%d][%d][%d][%d] = %d
" , cur , l1 , r1 , l2 , r2 , ans ) ;
return dp[cur][l1][r1][l2][r2] = ans ;
}
void solve ( int T ) {
scanf ( "%d%d%d%d" , &L1 , &R1 , &L2 , &R2 ) ;
clr ( vis , 0 ) ;
int ans = dfs ( 30 , 0 , 0 , 0 , 0 ) ;
printf ( "Case #%d: %d
" , T , ans ) ;
}
int main () {
int T ;
scanf ( "%d" , &T ) ;
For ( i , 1 , T ) solve ( i ) ;
return 0 ;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HDU] 4089 활성화 확률 DPdp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.