智力测试题

题目数据卡的比较严，本题主要考察选手面对简单题能不能考虑周全，把所有情况都考虑到位。

采集灵石题解

首先，第一个贪心处理并不难想。对于每个浮岛，如果前往的灵石花费比在该浮岛能得到的灵石 还多，那么就不应当前往这个浮岛。
如果前往浮岛的灵石花费和能得到的灵石数量相等，前往也没有意义，也可以不前往。 这样，我们只需要处理那些能够赚取灵石的浮岛即可。
接下来的问题在于，很可能牛牛初始的灵石数量无法前往那些浮岛。如何判断哪些浮岛能够抵达
呢?
我们可以发现，对于当前没有前往过的且激活传送阵花费最小的能赚灵石的浮岛，如果牛牛都不
能前往，那么所有没有前往过的且能赚灵石的浮岛就都不能前往了。 也就是说我们应当对这些能赚灵石的浮岛按照激活传送阵的费用由小到大排序，这样我们可以从能前往的浮岛开始一点一点攒灵石，可能一些本来不能前往的浮岛也就能前往了。但当所有能前往的 浮岛都去过了，剩下的浮岛还是去不了的时候，那就没有办法了。

跳跃的排列

有个很显然的观察，如果我们将 连向它对应的 ，那么形成了一棵”毛毛虫“：

“毛毛虫”的“脚”的部分，在一次跳跃之后，变成了对应的“身体”部分。而“毛毛虫”的“身体”部分满足从左到右下标依次递减，因此进行至多 次操作之后，序列将不会再跳跃。

现在问题就变成了判断是否需要操作，显然只有序列为 的时候答案是 ，其他情况答案均为 。

时间复杂度 。

防御法阵题解

因为今年普及组大纲中增加了区间动态规划知识点，所以特别征集了区间动态规划模板题目。
对于每一块城墙而言，使用01背包就可以计算出在 时间内最大经验值 。
看到只能破坏相邻的城墙，并且还有较为复杂的加成，便很容易想到这里可以用区间dp的方式处理。
下面是普通dp到区间dp的一个思路过程。
我们可以借助下面这张简图来理解区间dp的思路。

对于上面这一大段城墙，只可能是由这两种方式破坏，一种是先破坏左边一大段（红色）之后破坏了右边这一块城墙（蓝色），另一种是先破坏右边一大段之后破坏了左边这一块城墙。
那么对于一整段城墙而言（左端点为 ，右端点为 ），我们可以通过这样的思路得到一个转移方程（表示从 到 的城墙的最大经验值） (*2中，一是新破坏的蓝色部分加成，一是要加上原有的这一段的经验值）
但是，麻烦也来了，我们发现，要想知道一整段的最大经验值，就需要知道比这一整段少一块的城墙的最大经验值。这就导致上面这个式子利用循环进行递推并不容易。
怎样解决这个问题呢？再次观察这个情况，我们发现我们是按照一段城墙块数依次增多进行递推的。那么我们可以换一种表达方式。这一次，用 表示从 开始，一共有 块的城墙的最大经验值。对应状态转移方程为：
这样，只要按照 由小到大的顺序遍历 即可。这就是区间dp的状态转移方程的来历。
最后，上代码：

#include <bits/stdc++.h>
using namespace std;

int fazhen[30][2],k,fdp[300];
long long int dp[10010][110];
int m,n,t;

int main(){
    cin>>n>>m>>t;
    for(int i=1;i<=n;i++){
        cin>>k;
        for(int j=0;j<k;j++){
            cin>>fazhen[j][0]>>fazhen[j][1];
        }

        memset(fdp,0,sizeof(fdp));
        for(int j=0;j<k;j++){
            for(int v=t;v-fazhen[j][1]>=0;v--){
                fdp[v]=max(fdp[v],fdp[v-fazhen[j][1]]+fazhen[j][0]);
            }
        }
        dp[i][1]=fdp[t];
    }

    for(int l=2;l<=m;l++){
        for(int i=1;i<=n-l+1;i++){
            dp[i][l]=max(2*dp[i][l-1]+dp[i+l-1][1],2*dp[i+1][l-1]+dp[i][1]);
        }
    }

    long long int ans=0;
    for(int i=1;i<=n-m+1;i++){
        ans=max(dp[i][m],ans);
    }
    cout<<ans;
    return 0;
}