题目描述

小a正在玩一款星际探索游戏，小a需要驾驶着飞船从1号星球出发前往n号星球。其中每个星球有一个能量指数p。星球i能到达星球j当且仅当pi>pj。
同时小a的飞船还有一个耐久度t，初始时为1号点的能量指数，若小a前往星球j，那么飞船的耐久度会变为t⊕pj(即t异或pj，关于其定义请自行百度)
小a想知道到达n号星球时耐久度最大为多少

注意：对于每个位置来说，从它出发可以到达的位置仅与两者的p有关，与下标无关

输入描述:

第一行一个整数n，表示星球数
接下来一行有n个整数，第i个整数表示pi

输出描述:

一个整数表示到达n号星球时最大的耐久度
若不能到达n号星球或到达时的最大耐久度为0，则输出−1

输入

5
234 233 123 2333 23

输出

253

备注:

1⩽n,∀pi⩽3000

先上代码

#include <cstdio>
#include <cstring>
const int maxn = 1 << 12;  //3000

bool dp[maxn];  //判断当前耐久度是否可达
int exp[3005], ex[3005]; //ex[]是有可能到达的星球的能量

int main()
{
    int n, pos, ans;
    while(~scanf("%d", &n))
    {
        memset(dp, 0, sizeof(dp));
        for(int i=0; i<n; ++i)
            scanf("%d", &exp[i]);
        if(exp[0] <= exp[n-1]){  //1号星球的能量比n好星球的能量小或相等
            puts("-1"); continue;
        }
        pos = 0;
        dp[exp[0]^exp[n-1]] = true;  //1号到n号星球可达的耐久度
        for(int i=1; i<n-1; ++i)
        {
            if(exp[i] < exp[0] && exp[i] > exp[n-1])
                    ex[pos++] = exp[i]; //初步判断有可能到达的星球的能量
        }
        for(int i = 0; i<pos; ++i){
          /*如果之前的dp[j^ex[i]]为true(之前能达到j^ex[i]),
            那么取当前这个ex[i]，得j^ex[i]^ex[i]=j，
            说明j也是可以达到的，于是只要dp[j^ex[i]]为true，dp[j]就为true
         */
            for(int j = maxn-1; j>=0; --j)
            {
                dp[j] |= dp[j^ex[i]];  //之前dp[j]已经为true，则不取当前的ex[i]，dp[j]保持为true，表示j可达
            }
        }
        for(int i = maxn-1; i>=0; --i)
        {
            if(dp[i]) //从大到小，如果当前耐久度可达
            {
                ans = i; break;
            }
        }
        printf("%d\n", ans ? ans: -1);
    }
    return 0;
}