题目

有一直线型展台共有 m 个展位，按该展位离入口处的远近顺序编号，其编号分别为 1、2、……、m；其中只有 n 个是展示新技术的展位，最后一个展示新技术的展位编号为 m。
这次调研分两个小组进行，每个小组最多调研连续的 10 个展位，且每个小组调研的展位至少相隔 2 个展位。
乐乐希望你设计一种安排方案，使领导调研更多的展示新技术的展位。

输入：
第一行只有一个正整数：n，表示展示新技术的展位数
第二行共有 n 个正整数，依次表示新技术展位的编号

输出：
只有一行且只有一个正整数：领导调研过的不同的新技术展位数

对于 30%的数据， 1 <= n <= m <= 10
对于 70%的数据， 1 <= n <= m <= 1 000
对于 100%的数据， 1 <= n <= m <= 1 00 000

样例

样例输入

5  
1 3 12 21 8

样例输出

5

题目意思翻译

在当时比赛的时候，我因为这道题没看懂啥意思卡了很长时间，经过学长的解释，我终于整明白了。。。

有一个调研团队要去一个直线展台调研高新技术展台的情况，现在他们分成了两个调查组，每个组可以调研连续的1~10个展台，但是要求这两个调查组调查的展台不能有重复的部分，并且两个组之间相差两个展台（比如前一个组调查了1~10，后一个组就不能从11和12开始调研了，只能从13开始）。
问最多能调查几个高新技术展台。

解析

这道题比赛的时候我一点头绪也没有（主要是没看懂啥意思，实际上即使看懂了我也不会做），但是经过朱桑学长冥思苦想后，朱桑提出了一个贼棒的做法。总的来说思路并不复杂， 但是有很多细节和技巧值得考虑。

可以这样考虑，这两个调查组肯定是一个在前面几个展台调查，一个在后面几个展台调查。

划定活动范围

设有n个展台，我可以直接把这个直线展台切成两部分，一个是[1,k-3]这一部分，一个是[k,n]这部分，[k-2,k-1]这俩展台根据题意，没法被调研到，并且根据题意不存在某个组啥展台也没调研的情况。

很明显，我这样切，相当于给这两个组划定了他们的活动范围，通过让k取得所有的可能性，我可以完成对所有情况的判断。

遍历方式的考量（倒着枚举划分点）

前一个组的活动范围是[1,k-3]，后一个组的活动范围是[k,n]，显然，我的意思是按照后一个组的左端点划开活动范围。为什么呢？
这道题的技巧性在于，如果选择从后往前遍历的方式，问题会简单很多。

假设我在k=p的时候求得了前一个组和后一个组的最优解，现在我想看k=p+1的时候的情况。
如果我不这样划分了，我按第一个组的右端点划分，我把这个右端点从前往后挪，对于后一个组而言，那意思就是问我，在原来最优解的情况下，删掉某个点，最优解是多少。Excuse me？这求起来也忒复杂了。
但是如果我按后一个组的左端点，从右往左挪动，那意思就是问我，原来最优解是这样，现在我加进去一个点，最优解是多少？这看起来就是一个普普通通的DP了，比之前的问题顺当多了。

这个时候问题来了，诶？后面那个区间已知上一个状态最优解，加进去一个点求最优解，嗯，确实简单了，那前一个区间呢？前一个区间说白了变成了删一个点求最优解了啊，这太坑爹了，没解决本质问题，你只是把这个问题从后一个区间挪到前一个区间了。

嗯，说的很对。所以前一个区间我们可以考虑构建一个这样的数组f，f[i][j]我可以表示为从第i个位置，到第i+j-1个位置（j的意思其实是这一段的长度了，j<=10）这段的高新技术展台个数。
求解第一个组的最优解的时候，f[i][j]（到不了10的话按最长长度取）表示的就是左面的解了。
这里有个问题。嗯？枚举到每个左侧活动范围的时候，i是不是需要遍历一遍啊？其实在长度尽可能取10的时候，i直接取成右端点在这个范围最右侧的时候的情况就可以了。因为随着分界点从右往左动，i自然而然就把所有可能性给取了。

整体思路

输入数据，得出展台最右侧m。
维护一个f[i][j]数组，表示从i开始，长度为j这段范围的高新技术展台数量。
设计一个右侧活动范围最优解查询函数q，准备对右侧进行DP分析最优解。
程序的主干部分是一个二重循环，第一重循环是左侧区间的长度（f[i][j]里的j），第二层是左侧活动范围右端点（改成右侧活动范围左端点是一个意思，就是枚举活动范围的划分），求解左右最优，加起来跟全局最优比较求最大值。

代码

import java.io.*;

public class Main {

    //这破题输入输出要优化不然会超时
    //    public static Scanner scanner = new Scanner(new BufferedInputStream(System.in));
    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    static int n, m = 0;
    static int fuck = 0;
    static int[] arr = new int[233333];

    static int[] sum = new int[233333];
    static int[][] f = new int[233333][15];

    static int shit = 0;

    public static void main(String[] args) throws IOException {

        n = Integer.parseInt(reader.readLine().trim());
        String[] arg = ("0 " + reader.readLine()).split(" ");
        for (int i = 1; i <= n; i++) {
            int x = Integer.parseInt(arg[i]);
            arr[x] = 1;
            m = Math.max(m, x);
        }

        init();

        for (int i = 1; i <= 10; i++) {
            shit = 0;
            for (int j = m - i - 2; j >= 1; j--) { //左活动范围右端点
                fuck = Math.max(fuck, f[j][i] + q(i + j + 2, m));
            }
        }

        writer.write(fuck + "");

        reader.close();
        writer.flush();
        writer.close();
    }

    public static void init() {
        //sum
        for (int i = 1; i <= m; i++)
            sum[i] = sum[i - 1] + arr[i];

        //f
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= 10; j++) {
                if (i + j - 1 > m) continue;
                else f[i][j] = sum[i + j - 1] - sum[i - 1];
            }
        }

    }

    public static int q(int l, int r) {
        if (r - l + 1 < 10) return shit = Math.max(shit, f[l][r - l + 1]);
        return shit = Math.max(shit, f[l][10]); //长度最多10
    }
}