HDU 4293

题意：有 n 个人，可任意分成若干组，然后每个人各提供一个信息，表示他们组前面有多少个人，后面有多少个人。问最多有多少个信息是真实的的。

思路：

这道题一开始给我的印象是什么乱七八糟的东西，后来也没想通到底该怎么做，好在赛后百度在手天下我有：）

我们可以把 这n个人看成一段区间 [1,n]。
设每个人的信息是a、b，则这个信息代表了他们组所在的区间 [a+1,n-b]。

若a+b>n,显然撒谎，跳过不做处理。

我们用一个Map[i][j]数组将同在一区间[i,j]的人数纪录下来，纪录过程中若Map[i][j] > n-i-j则说明提供[i,j]区间消息的人里有人撒谎，略过不计，令Map[i][j] = n-i-j；

问题转化成了在 [1,n] 这段区间中分布的若干个带有权值的区间，问如何选取一些不相交的区间，使权值之和最大。

我们用dp[i]表示[1,i]区间权值之和的最大值，转移方程为dp[i] = max(dp[i],dp[j]+map[j][i]).

?

code:

?

/*
* @author Novicer
* language : C++/C
*/
#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
         
        
       
      
     
    
   
  

?

?