链接:https://ac.nowcoder.com/acm/contest/317/C
来源:牛客网
小a正在玩一款星际探索游戏,小a需要驾驶着飞船从11号星球出发前往nn号星球。其中每个星球有一个能量指数pp。星球ii能到达星球jj当且仅当pi>pjpi>pj。
同时小a的飞船还有一个耐久度tt,初始时为11号点的能量指数,若小a前往星球jj,那么飞船的耐久度会变为t⊕pjt⊕pj(即tt异或pjpj,关于其定义请自行百度)
小a想知道到达nn号星球时耐久度最大为多少
同时小a的飞船还有一个耐久度tt,初始时为11号点的能量指数,若小a前往星球jj,那么飞船的耐久度会变为t⊕pjt⊕pj(即tt异或pjpj,关于其定义请自行百度)
小a想知道到达nn号星球时耐久度最大为多少
注意:对于每个位置来说,从它出发可以到达的位置仅与两者的pp有关,与下标无关
输入描述:
第一行一个整数nn,表示星球数
接下来一行有nn个整数,第ii个整数表示pipi
输出描述:
一个整数表示到达nn号星球时最大的耐久度
若不能到达nn号星球或到达时的最大耐久度为00则输出−1−1
示例1
备注:
1⩽n,∀pi⩽30001⩽n,∀pi⩽3000
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = ;
int a[maxn];
int b[maxn];
int vis[maxn], n;
void dfs(int d, int u){
if (vis[d] || u >= n)return;
vis[d] = ;
for (int i = ; i <= n; ++i){
if (d > a[i]){
int t = d^a[i];
b[i] = max(b[i], t);
if (!vis[t])dfs(t, i); //如果出现过的话就不再就不可以。
}
}
} int main()
{
cin >> n;
for (int i = ; i <= n; ++i)
cin >> a[i];
dfs(a[], );
if (b[n])cout << b[n] << endl;
else cout << - << endl;
}