SRM 647 DIV2 Middle - TravellingSalesmanEasy (○)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13631&rd=16279
・M個の都市があり、その訪問順が決まっている。
・複数のアイテムについて、そのアイテムを売った時の利益と、そのアイテムを売ることができる都市のペアが与えられる。
・アイテムについて、その都市を訪問するごとにひとつ売ることができる。
・このとき、得られる最大の利益を求める。
解き方
・訪問順が決まっており、かつ一つのアイテムについて売ることのできる都市は１つであるので、
貪欲法で解くことができる。
計算量はO(１００＊２５００＝２．５＊１０＾５)なので間に合う。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class TravellingSalesmanEasy {
public: int getMaxProfit(int M, vector<int> profit, vector<int> city, vector<int> visit) {
int ret=0;
int n=profit.size();
int used[n];
memset(used,0,sizeof(used));
FORE(i,0,visit.size()){
int idx=-1,score=0;
FORE(j,0,n)if(!used[j] && city[j]==visit[i] && score<profit[j]){
score=profit[j];
idx=j;
}
if(idx!=-1){
used[idx]=1;
ret+=profit[idx];
}
}
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class TravellingSalesmanEasy {
public: int getMaxProfit(int M, vector<int> profit, vector<int> city, vector<int> visit) {
int ret=0;
int n=profit.size();
int used[n];
memset(used,0,sizeof(used));
FORE(i,0,visit.size()){
int idx=-1,score=0;
FORE(j,0,n)if(!used[j] && city[j]==visit[i] && score<profit[j]){
score=profit[j];
idx=j;
}
if(idx!=-1){
used[idx]=1;
ret+=profit[idx];
}
}
return ret;
}
};
