小a与星际探索（C++）
题目描述
小a正在玩一款星际探索游戏，小a需要驾驶着飞船从1号星球出发前往n号星球。其中每个星球有一个能量指数p。星球i能到达星球j当且仅当。
同时小a的飞船还有一个耐久度t，初始时为1号点的能量指数，若小a前往星球j，那么飞船的耐久度会变为(即t异或，关于其定义请自行百度)小a想知道到达n号星球时耐久度最大为多少。
注意：对于每个位置来说，从它出发可以到达的位置仅与两者的p有关，与下标无关。
输入描述:
第一行一个整数n，表示星球数
接下来一行有n个整数，第i个整数表示
输出描述:
一个整数表示到达n号星球时最大的耐久度
若不能到达n号星球或到达时的最大耐久度为0则输出−1
示例1
输入
3
457 456 23
输出
478
说明
小a有两种方法到达3号星球
第一种：1→2→3，最终耐久度为457⊕456⊕23=22
第二种：1→3，最终耐久度为457⊕23=478
示例2
输入
4
2 4 4 2
输出
-1
示例3
输入
5
234 233 123 2333 23
输出
253
备注:
1⩽n,∀⩽3000
解题代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 3050;
int p[N];//存储飞船能量
int tmp[N];
int a[N];
int n,m;
int main()
{
cin >> n;//星球数
for(int i=1;i<=n;++i) cin >> p[i];//每个星球的能量值
tmp[++m] = p[1];//tmp[1]为飞船初始时耐久度t为1号星球的能量指数
tmp[++m] = p[n];//tmp[2]为第n号星球的能量指数
if(p[1]<=p[n])//星球i能到达星球j当且仅当pi>pj，所以当1号星球的能量小于n号星球时，不能到达，输出-1
{
cout << "-1" << endl;
return 0;
}
/*把符合条件、可以经过的星球能量指数存储到tmp数组中*/
for(int i=2;i<n;++i)//从第二个星球到第n-1个星球遍历
if( p[i]<p[1] && p[i]>p[n] )//可以经过第i个星球的条件
tmp[++m] = p[i];//存储第i个星球的能量指数
/*经典动态规划0-1背包问题的类似代码*/
for(int i=3;i<=m;i++)//遍历除了1号和n号星球且符合条件星球的能量值
for(int j=12;j>=0;j--)//开到2的12次方就够3000了
if( ( tmp[i]>>j ) & 1 )//tmp[i]>>j等价于tmp[i]/pow(2,j),而n&1等价于n%2（用来判断奇偶）
{
if(a[j]==0) { a[j] = tmp[i]; break; }
else tmp[i] ^= a[j];
}
/*构造最优解*/
int ans = p[1]^p[n];//如果一次性从1号到达n号星球的耐久度
for(int i=12;i>=0;i--)
ans = max(ans,ans^a[i]);//分治思想，最优子解
cout << (ans>0?ans:-1) << endl;
return 0;
}
笔记：
附dp 0-1背包问题关键代码：
//0-1背包问题关键代码
//c[i][j]表示背包容量为j，可选物品为i,i+1,……,n时的最优解，0-1背包问题的最优值为c[1][m]
void knapsack()
{
int jMax = min(w[n]-1,m);//背包可承受最大重量和物体n的重量-1中较小数
int i,j;
//初始化c[n][j]
//当j<jMax时，c[n][j]为0
//例：假设jMax = w[n]-1，即背包可以容纳物体n，则在j<=jMax时，c[n][j]=0，w[n]<=j<=m时，c[n][j]=v[n]
for(j=0;j<=jMax;++j) c[n][j]=0;
for(j=w[n];j<=m;++j) c[n][j]=v[n];
for(i=n-1;i>1;--i)
{
jMax=min(w[i]-1,m);
for(j=0;j<=jMax;++j) c[i][j]=c[i+1][j];
for(j=w[i];j<=m;++j) c[i][j]=max(c[i+1][j],c[i+1][j-w[i]]+v[i]);
}
c[1][m]=c[2][m];
if(m>=w[1]) c[1][m]=max(c[1][m],c[2][m-w[1]]+v[1]);
}
//构造最优解
void traceBack(int *x)
{
int i,j;
j = m;
for(i=1;i<n;++i)
{
if( c[i][j]==c[i+1][j] ) x[i]=0;
else
{
x[i] = 1;
j -= w[i];
}
x[n]=(c[n][j])?1:0;
}
}
附几个动态规划讲解的网址：
https://blog.csdn.net/cr496352127/article/details/77934132
https://blog.csdn.net/Hearthougan/article/details/53869671
https://blog.csdn.net/weixin_39059738/article/details/79924049
https://blog.csdn.net/xp731574722/article/details/70766804
https://blog.csdn.net/smallhc/article/details/78666615