dp hdu5653 xiaoxin and his watermelon candy

题意：有n个箱子排成一排，有m个炸弹。位置告诉你。如今炸弹的左边伤害和右边伤害能够自己控制，要求每一个炸弹炸的箱子数的累乘，输出答案取log2并乘以1e6

思路：直接2for xjb搞即可了。大概就是某个区间里刚好仅仅有一个炸弹时，就是满足的，然后就从前面往后面更新一下

#include <map>

#include <set>

#include <cmath>

#include <ctime>

#include <stack>

#include <queue>

#include <cstdio>

#include <cctype>

#include <string>

#include <vector>

#include <cstring>

#include <iomanip>

#include <iostream>

#include <algorithm>

#include <functional>

#define fuck(x) cout<<"["<<x<<"]"

#define FIN freopen("input.txt","r",stdin)

#define FOUT freopen("output.txt","w+",stdout)

using namespace std;

typedef long long LL;

typedef pair<int, int> PII;

const int MX = 2e3 + 5;

const int W = 1e6;

int A[MX];

double dp[MX];

int main() {

    int T, n, m; //FIN;

    scanf("%d", &T);

    while(T--) {

        scanf("%d%d", &n, &m);

        memset(A, 0, sizeof(A));

        memset(dp, 0, sizeof(dp));

        for(int i = 1; i <= m; i++) {

            int t; scanf("%d", &t);

            t++; A[t] = 1;

        }

        for(int i = 2; i <= n; i++) A[i] += A[i - 1];

        for(int i = 1; i <= n; i++) {

            for(int j = 0; j < i; j++) {

                if(A[i] - A[j] == 1) {

                    dp[i] = max(dp[i], dp[j] + log2(1.0 * i - j));

                }

            }

        }

        printf("%.0f\n", floor(dp[n] * W));

    }

}