题目描述其中|S|为集合S中元素个数。一、题意解释我们最终需要求得的是最大集合中的元素个数也就从任一位置开始能跳到的最大不同元素个数注意我们可以通过不同方式来跳也就是说n5时, 如果条件允许我们可以1-2-5,1-3-4,此时集合中元素为{12345}五个数。二、思路思考对与当前位置i我们在当前位置起跳的最多不同元素个数记为f[i]从两个位置得来一个是ic[i],另一个是2*i,所以我们发先了重叠子问题要计算f[i]我们都可以通过f[ic[i]],f[2*i],来计算当然不能越界。这就顺理成章的想到了动态规划。我们发现要计算f[i]需要先计算它后面的f[ic[i]]f[2*i]所以我们用倒叙遍历先计算大的这样就可以顺利递推啦所以我们让f[i]为从第i个石头开始起跳能跳到权值不同的石头数。大致形式for (int i n; i 1; i--) { if (i c[i] n) { f[i] ; } if (2*i n) { f[i] ; } ans max(ans, f[i]); }三、状态转移这是最难的一部分我们需要计算的是集合中的元素个数是不能有重复的所以for (int i n; i 1; i--) { f[i] 1; if (i c[i] n) { f[i] f[ic[i]]; } if (2*i n) { f[i] f[2*i]; } ans max(ans, f[i]); }这样就不行了这样没有去重会导致重复元素进入集合是不对的。可是我们怎么去重呢我们想到位运算中的’或‘运算可以解决这个问题。如果我们能让相同的权值取或那么多个相同的权值不就变成一个了吗1 | 1 1也就是把集合用二进制数表示。但是还要注意我们必须把相同的权值放到同一个位置上他们才能进行或操作。那我们怎么确定这个位置呢把它自己当位置就行了权为1那么就在1这个位置为1权为10就在10这个位置赋为1这样再遇到同权的就可以直接取或了如{145}表示为110010{135}表示为101010他们取或就是111010也就是集合{1345}我们暂且先用一个叫g的容器存这个二进制数也就是集合每到一个石头我们令g[c[i]] 1(也就是集合中加入从c[i]如果已经为1那么再赋1相当于没加入集合元素个数没变)每次g[i] | g[ic[i]];g[i] | g[2*i];此时g[i]中1的数量就是f[i];这样大大致就可以了但是有容器是可以直接作为一个二进制数然后能直接操作里面内容的吗还真有bitset具体bitset的方法我就不多赘述大家可以字形搜索我就把我们需要的方法count()告诉大家这个方法可以计算这个对象的1的个数具体上代码吧#include bits/stdc.h #define int long long using namespace std; const int N 4e4; signed main() { ios::sync_with_stdio(false); cin.tie(0); int n, ans 0; cin n; vectorint c(n1, 0); vectorbitsetN1 f(n1);//这个有没有疑惑会不会爆内存MLE for (int i 1; i n; i) { cin c[i]; } for (int i n; i 1; i--) { f[i][c[i]] 1; if (i c[i] n) { f[i] | f[ic[i]]; } if (2*i n) { f[i] | f[2*i]; } ans max(ans, (int)f[i].count());//count方法时间复杂度是多少不会TLE吧 } cout ans \n; return 0; }注释对于第一个问题我们稍做解释bitsetn占用的空间为n byten位所以我们最大使用空间为(N1)*(N1)byte我们就当N^2来计算大致为8e8 byte,而对于int型数组我们最大约为6e7一个int型变量占4字节一个字节8位所以最终占位为4*8*6e7 1.92e9,大于8e8,所以我们呢内存是不会爆的对于第二个问题不是我能解答的感兴趣可以自行搜索反正是不会爆就对了。