POJ 1160 （区间DP+四边形优化）

这个转移方程不好想，尤其是一段值的解是中间，不明觉厉。dp[i][j] 用i个邮局，覆盖前j个村庄的最小值。

还有就是区间dp的平行四边形优化，这个题的转移方程并不是“区间DP”，所以枚举状态要逆着（很花时间），且用一个邮局覆盖都是从0断开了相当于没有断开。

类比于石子归并，矩阵链乘等标准区间DP，其所需状态之前就已经获得，不用倒推

#include 
  
   
#include 
   
     #include 
    
      using namespace std; const int NN=310; const int INF=0x7fffffff; int n,m; int s[NN],dp[NN][NN],w[NN][NN],p[NN][NN]; void get_w()//求在i~j号村庄间建一个邮局的最小距离和 { for (int i=1; i
     
      
 
      
//直线取石子问题的平行四边形优化：

#include 
       
        
#include 
        
          #include 
         
           using namespace std; const int INF = 1 << 30; const int N = 1005; int dp[N][N]; int p[N][N]; int sum[N]; int n; int getMinval() { for(int i=1; i<=n; i++) { dp[i][i] = 0; p[i][i] = i;//这个自己跟自己乘自然是以自己为分割了。 } for(int len=1; len