소 손님 '열 렸 다' 대회 1 - D 筱 ma 의 미로 탐험
제목 설명
조 마 는 즐 거 운 남자 아이 다.겨울방학 이 마침내 왔 다.미진×nn×n 의 행렬 A, 각 칸 에 하나의 숫자 가 있다.입 구 는 왼쪽 상단 (1, 1) 에 있 고 출구 는 오른쪽 아래 (n, n) 에 있 습 니 다.한 걸음 한 걸음 아래로 또는 오른쪽으로 한 칸 만 이동 할 수 있 습 니 다.마지막 으로 얻 을 수 있 는 경험 치 는 초기 경험 e 와 경로 에서 거 친 모든 수의 가중치 가 다 르 거나 합 쳐 집 니 다.쿠 마 가 얻 을 수 있 는 최대 경험 치 를 구하 세 요.
입력 설명:
n e。
n ， n ， A。출력 설명:
， 。예시 1
입력
복제 하 다.
5 2
3 4 7 2 6
3 5 2 9 0
3 8 5 7 3
2 5 3 1 4
9 8 6 3 5출력
복제 하 다.
15비고:
1≤n≤20;0≤e,Ai,j<231주소:https://ac.nowcoder.com/acm/contest/545/D
아이디어: 절반 DFS + 01 사전 트 리
이 문 제 는 순수 DFS 를 사용 하면 시간 이 초과 되 지만 왼쪽 위 에서 오른쪽 아래 까지 반드시 대각선 (x, x) 의 위 치 를 지나 기 때문에 왼쪽 위, 오른쪽 아래 양 끝 에서 대각선 (x, x) 의 위 치 를 찾 아 01 사전 트 리 로 차이 점 이나 최대 치 를 구하 면 된다.
Code:
#include
using namespace std;
const int MAX_N=25;
const int MAX_S=3200005;
int n,e,ans;
int a[MAX_N][MAX_N];
int Trie[MAX_N][MAX_S][2],num[MAX_N];
void Insert(int x);
int Query(int x);
void DFS1(int k,int s,int Sum);
void DFS2(int k,int s,int Sum);
int main()
{
ios::sync_with_stdio(false);
cin>>n>>e;
for(int i=1;i<=n;++i)
for(int j=1,x;j<=n;++j)
cin>>a[i][j];
DFS1(1,1,e);
DFS2(n,n,0);
cout<=0;--i)
{
t=(x>>i)&1;
if(!Trie[k][u][t]) Trie[k][u][t]=++num[k];
u=Trie[k][u][t];
}
}
int Query(int k,int x)
{
int t,u=0,res=0;
for(int i=31;i>=0;--i)
{
t=(x>>i)&1;
if(Trie[k][u][!t]) res|=(1<n) return;
if(k+s>n+1) return;
if(k+s==n+1){
Insert(k,Sum^a[k][s]);
return;
}
int pp=0;
for(int i=s;i<=n-k+1;++i)
{
pp^=a[k][i];
DFS1(k+1,i,Sum^pp);
}
Insert(k,Sum^pp);
}
void DFS2(int k,int s,int Sum)
{
if(k<1) return;
if(k+s=n-k+1;--i)
{
pp^=a[k][i];
DFS2(k-1,i,Sum^pp);
}
Sum^=pp^a[k][n-k+1];
ans=max(ans,Query(k,Sum));
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
2 단 대기 열 문제 풀이이 문제 의 가장 직접적인 해법 은 모든 미끄럼 창 을 직접 옮 겨 다 니 며 각 창의 최대 치 를 찾 으 면 된다.모두 N - k + 1 개의 미끄럼 창 이 있 고 미끄럼 창 마다 k 개의 요소 가 있 기 때문에 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
