1C.小a与星际探索（C++）

本文主要是介绍1C.小a与星际探索（C++），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

小a与星际探索（C++）

点击做题网站链接

题目描述
小a正在玩一款星际探索游戏，小a需要驾驶着飞船从1号星球出发前往n号星球。其中每个星球有一个能量指数p。星球i能到达星球j当且仅当$p_i>p_j$。
同时小a的飞船还有一个耐久度t，初始时为1号点的能量指数，若小a前往星球j，那么飞船的耐久度会变为$t\oplus p_j$(即t异或$p_j$，关于其定义请自行百度)小a想知道到达n号星球时耐久度最大为多少。
注意：对于每个位置来说，从它出发可以到达的位置仅与两者的p有关，与下标无关。

输入描述:
第一行一个整数n，表示星球数
接下来一行有n个整数，第i个整数表示$p_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,∀$p_i$⩽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

这篇关于1C.小a与星际探索（C++）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---