ACM模版

描述

题解

这道题虽然过了，但是不得不说是打了内存的擦边球，因为前所未有的使用了short int类型，不然就爆内存了，这也是很措手不及。

这道题的坑不止这一点，题目说，从这N个数中找出若干数组成最长等差数列，所以，顺序上我们可以打乱，先进行一下排序是很有必要的。

最后不得不承认，这道题的dp思路是我之前所没有的，先固定一个端点，然后两边扫描，也是极其有趣，必须点个赞，以前做dp，总是想着单方向的，这一次算是见识到了双向dp的厉害了（随便叫的，也不知道叫啥比较合适）。

但是这种思路可以肯定的是，V2必挂，需要再考虑考虑别的算法，真是个不错的题~~~

代码

#include <cstdio>
#include <algorithm>

using namespace std;

int const MAXN = 10005;
int a[MAXN];
short int dp[MAXN][MAXN]; // dp[i][j]表示的是以i和j为前两个元素的序列

int main()
{
    int n, ans;
    while (scanf("%d", &n) != EOF)
    {
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
        }
        sort(a, a + n);
        for (int i = 0 ; i < n ; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                dp[i][j] = 2;  // 最小值为2
            }
        }
        ans = 2;
        for (int j = n - 2; j >= 1; j--)
        {
            int i = j - 1, k = j + 1;
            while (i >= 0 && k <= n - 1)
            {
                if (a[i] + a[k] < 2 * a[j])
                {
                    k++;
                }
                else if (a[i] + a[k] > 2 * a[j])
                {
                    i--;
                }
                else
                {
                    dp[i][j] = dp[j][k] + 1;
                    if (dp[i][j] > ans)
                    {
                        ans = dp[i][j];
                    }
                    i--;
                    k++;
                }
            }
        }
        printf("%d\n", ans);
    }

    return 0 ;
}