DP/四边形不等式

---

　　要求将一个可重集S分成M个子集，求子集的极差的平方和最小是多少……

　　首先我们先将这N个数排序，容易想到每个自己都对应着这个有序数组中的一段……而不会是互相穿插着= =因为交换一下明显可以减小极差

　　然后……直接四边形不等式上吧……这应该不用证明了吧？

 

　　MLE了一次：这次的w函数不能再开数组去存了……会爆的，直接算就行了= =反正是知道下标直接就能乘出来。

　　数据比较弱，我没开long long保存中间结果居然也没爆……（只保证最后结果不会爆int，没说DP过程中不会……）

1 //HDOJ 3480 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #define rep(i,n) for(int i=0;i
             
              =n;--i)12 #define pb push_back13 #define CC(a,b) memset(a,b,sizeof(a))14 #define SHOW_MEMORY(x) cout<
              
               >2;23 const double eps=1e-8;24 /*******************template********************/25 int dp[5010][N],n,m,a[N],s[5010][N],ans;26 void work(){27 n=getint(); m=getint();28 F(i,1,n) a[i]=getint();29 sort(a+1,a+n+1);30 F(i,1,m) F(j,1,n) dp[i][j]=INF;31 F(i,1,n){32 dp[1][i]=(a[i]-a[1])*(a[i]-a[1]);33 s[1][i]=0;34 }35 F(i,2,m){36 s[i][n+1]=n;37 D(j,n,i)38 F(k,s[i-1][j],s[i][j+1])39 if(dp[i-1][k]+(a[j]-a[k+1])*(a[j]-a[k+1])