座位調(diào)整
題目描述：
百度辦公區(qū)里到處擺放著各種各樣的零食。百度人力資源部的調(diào)研發(fā)現(xiàn)，員工如果可以在自己喜歡的美食旁邊工作，工作效率會(huì)大大提高。因此，百度決定進(jìn)行一次員工座位的大調(diào)整。
調(diào)整的方法如下：
1 ． 首先將辦公區(qū)按照各種零食的擺放分成 N 個(gè)不同的區(qū)域。（例如：可樂(lè)區(qū)，餅干區(qū)，牛奶區(qū)等等）。
2 ． 每個(gè)員工對(duì)不同的零食區(qū)域有不同的喜好程度（喜好程度度的范圍為 1 — 100 的整數(shù)， 喜好程度越大表示該員工越希望被調(diào)整到相應(yīng)的零食區(qū)域）。
3 ． 由于每個(gè)零食區(qū)域可以容納的員工數(shù)量有限，人力資源部希望找到一個(gè)最優(yōu)的調(diào)整方案令到總的喜好程度最大。
數(shù)據(jù)輸入：
第一行包含兩個(gè)整數(shù) N ， M ，（ 1<=N ， M<=300 ）。分別表示 N 個(gè)區(qū)域和 M 個(gè)員工。
第二行是 N 個(gè)整數(shù)構(gòu)成的數(shù)列 a ，其中 a[i] 表示第 i 個(gè)區(qū)域可以容納的員工數(shù)， (1<=a[i]<=M ， a[1]+a[2]+..+a[N]=M) 。
緊接著是一個(gè) M*N 的矩陣 P ， P （ i ， j ）表示第 i 個(gè)員工對(duì)第 j 個(gè)區(qū)域的喜好度。
答案輸出：
對(duì)于每個(gè)測(cè)試數(shù)據(jù)，輸出可以達(dá)到的最大的喜好程度。
輸入樣例
3 3
1 1 1
100 50 25
100 50 25
100 50 25
輸出樣例
175
static const int M = 3;
static const int N = 3;
static int capac[] = {1, 1, 1};
vector<int> eraseRow(const vector<int> &v, int i, int currentArea)
{
int colSize = N - currentArea;
vector<int> newVec;
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());
return newVec;
}
vector<int> eraseCol(const vector<int> &v, int currentArea)
{
vector<int> newVec;
for (int i = 0; i != v.size(); ++i)
{
if (i%(N-currentArea))
{
newVec.push_back(v[i]);
}
}
return newVec;
}
int getMax(vector<int> v, int numOfPeop, int numOfCapac, int currentArea = 0, int start = 0)
{
int sum = 0, max = 0;
int curr = currentArea;
if (numOfPeop < numOfCapac)
{
cerr<<"the numOfPeople is smaller than Capacity"<<endl;
return -1;
}
else if (numOfPeop == numOfCapac)
{
for (int i = 0; i != numOfCapac; ++i)
{
max += v[i];
}
}
else
{
vector<int> newVec;
if (numOfCapac == 1)
{
for (int i = 0; i <= numOfPeop - numOfCapac; ++i)
{
sum = v[i * (N - curr)];
newVec = eraseRow(v,i,curr);
newVec = eraseCol(newVec,curr);
if (curr < N)
{
sum += getMax(newVec, numOfPeop -1, capac[curr+1],curr+1);
}
max = (max > sum ? max:sum);
}
}
else
{
if (numOfCapac<1)
{
cerr<<"numOfCapacity is smaller than zero"<<endl;
return -1;
}
for (int i = 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);
}
}
}
return max;
}
void printVec(const vector<int>& v)
{
int delim = 1;
for (int i = 0; i != v.size(); ++i, ++delim)
{
cout<<v[i]<<"\t";
if (!(delim %3))
{
cout<<endl;
}
}
}
void main(int argc, char **argv)
{
ifstream ifs("IntrestArea.txt");
vector<int> v;
v.reserve(M*N);
int i;
while(ifs>>i)
{
v.push_back(i);
}
int max = getMax(v,M,capac[0]);
cout<<max<<endl;
}
多積累函數(shù)，才是最寶貴的。。。。并不是 要自己一定能夠編寫出來(lái)喲！！！多讀讀