题意：bc 77 div1 1003（中文题面）

分析：先不考虑将结果乘以 1e6。 设 dp[i] 为从前 i 个格子的状态可以获得的最大破坏指数。

那么我们可以枚举每个炸弹，该炸弹向左延伸的距离和向又延伸的距离。

设第 i 个炸弹破坏区间为 [l, r], 则 dp[r] = dp[l - 1] + log2(r - l + 1)。答案就是 dp[n - 1]。不要忘记最后要向下取整。

 

注：我对官方题解稍作解释，dp[i]代表前i个格子可以获得的最大破坏指数

但是更新的时候，需要注意，假设有 n 个炸弹，第 i 个炸弹的位置是o[i]

那么考虑处理到第i个炸弹，他能更新的dp[j]是有限制的，o[i]<=j<o[i+1]，因为一个炸弹的爆炸区域不可能跨过另外一个炸弹

更新dp[j]的也dp[k]也是有限制的，o[i-1]<=k<=o[i]，道理是一样的

然后看起来是三重循环，实际上很小

然后有一个小优化，事先把log2(1-2000)打出来，因为这个函数很慢

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;typedef long long LL;const int N=2e3+5;const int INF=0x3f3f3f3f;int o[N];double dp[N],val[N];int main(){ for(int i=1;i<=2001;++i) val[i]=log(i)/log(2); int T; scanf("%d",&T); while(T--){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=m;++i) scanf("%d",&o[i]),++o[i]; sort(o+1,o+1+m); memset(dp,0,sizeof(dp)); int c=m>1?o[2]:n+1; for(int i=o[1];i
             
              =o[i];--j) for(int k=o[i-1];k