Source

Problem Id:1160  User Id:Judas 
Memory:772K  Time:62MS
Language:C++  Result:Wrong Answer

Source 

 #include <iostream.h>
 #include <string.h>
 int n,m;
 int x[301];
 void main()
 {
 	int i,j,k,l,qs;
 	int p[301][301],gg[301][301],ff[301][31];
 	//gg[i][j] ????????i??j????????????????????????	457886728
 	//ff[j][i] ??????i????????j????????????????
 	memset(gg,0,sizeof(gg));memset(ff,0,sizeof(ff));	
	cin>>n>>m;	
 	for(i=1;i<=n;i++)	cin>>x[i]; 	
	for(i=1;i<=n;i++)	
		for(j=1;j<=n;j++)
		{
			if(i<=j)	p[i][j]=x[j]-x[i];
			else	p[i][j]=p[j][i];
		}
	for(k=1;k<=n;k++)	
		for(int nn=k;nn<=n;nn++)	
		{
			l=(nn+k)/2;
 			for(i=k;i<=nn;i++)	
				gg[k][nn]+=p[i][l];
		}
	for(i=1;i<=n;i++)	ff[1][i] = gg[1][i];
 	for(i=1;i<=n;i++)
 		for(j=2;j<=m;j++)
 		{
 			ff[j][i] = 2000000000;
 			for(k=j-1;k<=i;k++)
 			{
 				qs = ff[j-1][k] + gg[k+1][i];
 				if(qs<ff[j][i])		ff[j][i] = qs;
 			}
 		}
 		cout<<ff[m][n]<<endl;
 }