题目链接：这里
题意：
Problem Description
众所周知，度度熊喜欢的字符只有两个：B 和D。

今天，它发明了一个游戏：D游戏。

度度熊的英文并不是很高明，所以这里的D，没什么高深的含义，只是代指等差数列(等差数列百科)中的公差D。

这个游戏是这样的，首先度度熊拥有一个公差集合{D}，然后它依次写下N个数字排成一行。游戏规则很简单：

  1. 在当前剩下的有序数组中选择X(X≥2) 个连续数字；

  2. 检查1选择的X个数字是否构成等差数列，且公差 d∈{D}；

  3. 如果2满足，可以在数组中删除这X个数字；

  4. 重复 1−3 步，直到无法删除更多数字。

度度熊最多能删掉多少个数字，如果它足够聪明的话？

Input
第一行一个整数T，表示T(1≤T≤100) 组数据。

每组数据以两个整数 N，M 开始 。接着的一行包括 N 个整数，表示排成一行的有序数组 Ai。接下来的一行是 M 个整数，即给定的公差集合 Di。

1≤N,M≤300

−1 000 000 000≤Ai,Di≤1 000 000 000

Output
对于每组数据，输出最多能删掉的数字 。

Sample Input

3
3 1
1 2 3
1
3 2
1 2 4
1 2
4 2
1 3 4 3
1 2

Sample Output

3
2
4

解法：
区间dp

由于等差数列的性质，只考虑删除2个和删除三个的情况

如果要删除的话，就必须把中间的都删除，即dp[l+1,r-1]=(r-l-1)这种

知道这个之后，我们直接暴力转移就好了，复杂度n^3

//HDU 5693

#include <bits/stdc++.h>
using namespace std;
const int maxn = 305;
int a[maxn], c[maxn][maxn], dp[maxn][maxn];
int n, m, x;

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        memset(dp, 0, sizeof dp);
        memset(c, 0, sizeof c);
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for(int i = 1; i <= m; i++){
            scanf("%d", &x);
            for(int j = 1; j <= n; j++){
                for(int k = j+1; k <= n; k++){
                    if(a[k]-a[j] == x){
                        c[j][k] = 1;
                    }
                }
            }
        }
        for(int len = 1; len <= n; len++){
            for(int l = 1; l <= n; l++){
                int r = l + len;
                if(r > n) break;
                dp[l][r] = max(dp[l+1][r], dp[l][r-1]);
                if(c[l][r]&&dp[l+1][r-1]==(r-l-1)){
                    dp[l][r] = max(dp[l][r], dp[l+1][r-1]+2);
                }
                for(int i = l; i < r; i++){
                    dp[l][r] = max(dp[l][r], dp[l][i]+dp[i+1][r]);
                }
                for(int i=l+1; i<r; i++){
                    if(c[l][i]&&dp[l+1][i-1]==(i-l-1)){
                        dp[l][r] = max(dp[l][r], dp[l+1][i-1]+dp[i+1][r]+2);
                    }
                    if(c[i][r]&&dp[i+1][r-1]==(r-i-1)){
                        dp[l][r] = max(dp[l][r], dp[l][i-1]+ dp[i+1][r-1]+2);
                    }
                    if(c[l][i]&&c[i][r]&&a[i]-a[l]==a[r]-a[i]&&dp[l+1][i-1]==(i-l-1)&&dp[i+1][r-1]==(r-i-1)){
                        dp[l][r] = max(dp[l][r], r-l+1);
                    }
                }
            }
        }
        printf("%d\n", dp[1][n]);
    }
    return 0;
}