【HDOJ】【3480】Division DP/四边形不等式
要求将一个可重集S分成M个子集，求子集的极差的平方和最小是多少……
首先我们先将这N个数排序，容易想到每个自己都对应着这个有序数组中的一段……而不会是互相穿插着= =因为交换一下明显可以减小极差
然后……直接四边形不等式上吧……这应该不用证明了吧？
MLE了一次：这次的w函数不能再开数组去存了……会爆的，直接算就行了= =反正是知道下标直接就能乘出来。
数据比较弱，我没开long long保存中间结果居然也没爆……（只保证最后结果不会爆int，没说DP过程中不会……）
1 //HDOJ 3480 2 #include<cmath> 3 #include<vector> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<iostream> 8 #include<algorithm> 9 #define rep(i,n) for(int i=0;i<n;++i) 10 #define F(i,j,n) for(int i=j;i<=n;++i) 11 #define D(i,j,n) for(int i=j;i>=n;--i) 12 #define pb push_back 13 #define CC(a,b) memset(a,b,sizeof(a)) 14 #define SHOW_MEMORY(x) cout<<sizeof(x)/(1024.0)<<"KB"<<endl 15 using namespace std; 16 int getint(){ 17 int v=0,sign=1; char ch=getchar(); 18 while(!isdigit(ch)) {if(ch=='-') sign=-1; ch=getchar();} 19 while(isdigit(ch)) {v=v*10+ch-'0'; ch=getchar();} 20 return v*sign; 21 } 22 const int N=10010,INF=~0u>>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])<dp[i][j]){ 40 s[i][j]=k; 41 dp[i][j]=dp[i-1][k]+(a[j]-a[k+1])*(a[j]-a[k+1]); 42 } 43 } 44 ans=dp[m][n]; 45 } 46 int main(){ 47 int T=getint(); 48 F(i,1,T){ 49 work(); 50 printf("Case %d: %d ",i,ans); 51 } 52 return 0; 53 }