当前位置:   article > 正文

1C.小a与星际探索(C++)_c++星际探险家在其最新的宇宙探险中遭遇了一系列新的挑战。此次探险中,探险家的飞

c++星际探险家在其最新的宇宙探险中遭遇了一系列新的挑战。此次探险中,探险家的飞

小a与星际探索(C++)

点击做题网站链接

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

输入描述:
第一行一个整数n,表示星球数
接下来一行有n个整数,第i个整数表示 p i p_i pi

输出描述:
一个整数表示到达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 p_i pi⩽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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42

笔记:

附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;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37

附几个动态规划讲解的网址:
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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/714513
推荐阅读
相关标签
  

闽ICP备14008679号