ACM座位調整題目的解答

題目描述：

百度辦公區里到處擺放著各種各樣的零食。百度人力資源部的調研發現，員工如果可以在自己喜歡的美食旁邊工作，工作效率會大大提高。因此，百度決定進行一次員工座位的大調整。

調整的方法如下：

1 ． 首先將辦公區按照各種零食的擺放分成 N 個不同的區域。（例如：可樂區，餅干區，牛奶區等等）。

2 ． 每個員工對不同的零食區域有不同的喜好程度（喜好程度度的范圍為 1 — 100 的整數， 喜好程度越大表示該員工越希望被調整到相應的零食區域）。

3 ． 由于每個零食區域可以容納的員工數量有限，人力資源部希望找到一個最優的調整方案令到總的喜好程度最大。

數據輸入：

第一行包含兩個整數 N ， M ，（ 1<=N ， M<=300 ）。分別表示 N 個區域和 M 個員工。

第二行是 N 個整數構成的數列 a ，其中 a[i] 表示第 i 個區域可以容納的員工數， (1<=a[i]<=M ， a[1]+a[2]+..+a[N]=M) 。

緊接著是一個 M*N 的矩陣P ， P （ i ， j ）表示第 i 個員工對第 j 個區域的喜好度。

答案輸出：

對于每個測試數據，輸出可以達到的最大的喜好程度。

輸入樣例

3 3

1 1 1

100 50 25

100 50 25

100 50 25

輸出樣例

175
staticconstintM=3;
staticconstintN=3;
staticintcapac[]={1,1,1};
vectoreraseRow(constvector&v,inti,intcurrentArea)
{
intcolSize=N-currentArea;
vectornewVec;
newVec.reserve(v.size()-colSize);
newVec.insert(newVec.begin(),v.begin(),v.begin()+i*colSize);
newVec.insert(newVec.end(),v.begin()+(i+1)*colSize,v.end());
returnnewVec;
}
vectoreraseCol(constvector&v,intcurrentArea)
{
vectornewVec;
for(inti=0;i!=v.size();++i)
{
if(i%(N-currentArea))
{
newVec.push_back(v[i]);
}
}
returnnewVec;
}

intgetMax(vectorv,intnumOfPeop,intnumOfCapac,intcurrentArea=0,intstart=0)
{
intsum=0,max=0;
intcurr=currentArea;
if(numOfPeop{
cerr<<"the numOfPeople is smaller than Capacity"<return-1;
}
elseif(numOfPeop==numOfCapac)
{
for(inti=0;i!=numOfCapac;++i)
{
max+=v[i];
}
}
else
{
vectornewVec;
if(numOfCapac==1)
{
for(inti=0;i<=numOfPeop-numOfCapac;++i)
{
sum=v[i*(N-curr)];
newVec=eraseRow(v,i,curr);
newVec=eraseCol(newVec,curr);
if(curr{
sum+=getMax(newVec,numOfPeop-1,capac[curr+1],curr+1);
}
max=(max>sum?max:sum);
}
}
else
{
if(numOfCapac<1)
{
cerr<<"numOfCapacity is smaller thanzero"<return-1;
}
for(inti=start;i!=numOfPeop-numOfCapac;++i)
{
sum=v[i*(N-curr)];
newVec=eraseRow(v,i,curr);
sum+=getMax(newVec,numOfPeop-1,numOfCapac-1,curr,i);
max=(max>sum?max:sum);
}
}
}
returnmax;
}
voidprintVec(constvector&v)
{
intdelim=1;
for(inti=0;i!=v.size();++i,++delim)
{
cout<if(!(delim%3))
{
cout<}
}
}
voidmain(intargc,char**argv)
{
ifstream ifs("IntrestArea.txt");
vectorv;
v.reserve(M*N);
inti;
while(ifs>>i)
{
v.push_back(i);
}
intmax=getMax(v,M,capac[0]);
cout<}
多積累函數，才是最寶貴的。。。。并不是要自己一定能夠編寫出來喲！！！多讀讀