sss.cpp

石子合并问题 在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆

#include <stdio.h> 
#include <fstream.h> 
#include<stdlib.h> 
int n,money; 
struct ctype 
{ 
 int value; 
 int coin; 
}; 
template<class type> 
void make2Darray(type * * &x,int rows,int cols) 
{ 
 x=new type *[rows]; 
 for(int i=0;i<rows;i++) 
 x[i]=new type[cols]; 
} 
void swap(ctype &a,ctype &b) 
{  
ctype temp; 
temp=a; 
a=b; 
b=temp; 
} 
int partition(ctype array[],int p,int r) 
{ 
int i,j; 
ctype key; 
i=p; 
j=r+1; 
key=array[p]; 
while(true) 
{ 
while(array[++i].value<key.value); 
while(array[--j].value>key.value); 
if(i>=j) break;  
swap(array[i],array[j]); 
} 
array[p]=array[j]; 
array[j]=key; 
return j; 
} 
void quicksort(ctype array[],int p,int r)  
{ 
int q; 
if(p<r) 
{ 
q=partition(array,p,r); 
quicksort(array,p,q-1); 
quicksort(array,q+1,r); 
} 
} 
void main() 
{ 
 ifstream input("input.txt"); 
 ofstream output("output.txt"); 
 input>>n; 
 int * coins=new int[n+1]; 
 ctype * T=new ctype[n+1]; 
 for(int i=1;i<=n;i++) 
{ 
 input>>T[i].value; 
 input>>T[i].coin; 
} 
 input>>money; 
quicksort(T,1,n); 
for(i=1;i<=n;i++) 
{ 
coins[i]=T[i].coin; 
}
 int max=0; 
 for(i=1;i<=n;i++)  max+=T[i].coin; 
 max+=10;  
 int * min=new int[money+1];  
 min[0]=0; 
int * * cnum; 
 make2Darray(cnum,money+1,n+1); 
 for(i=0;i<=money;i++) 
 for(int j=1;j<=n;j++) 
 cnum[i][j]=0; 
if(T[1].value==1) {min[1]=1;cnum[1][1]=1;} 
else min[1]=max; 
 int j=2; 
 while(j<=money) 
{ 
 min[j]=max; 
 i=1;  
 while((i<=n)&&(j>=T[i].value)) 
 { 
   int coinumber=cnum[j-T[i].value][i]; 
 coinumber++; 
 if((min[j]>1+min[j-T[i].value])&&(coinumber<=T[i].coin)) 
 {  
  for(int k=1;k<=n;k++) cnum[j][k]=cnum[j-T[i].value][k]; 
  cnum[j][i]++; 
  min[j]=1+min[j-T[i].value]; 
 } 
 i++;  
 } 
   j++; 
} 
 if(min[money]!=max) output<<min[money]; 
 else output<<-1; 
}