問題
http://community.topcoder.com/stat?c=problem_statement&pm=12706&rd=15700
解き方
どの範囲のトーンを利用するか、という情報がわかれば
あとはその範囲内のトーンについてdurationが小さい順に選んでいけばよい。
コード
class GUMIAndSongsDiv1 {
public: int maxSongs(vector<int> duration, vector<int> tone, int T) {
int n=duration.size();
vector<pair<int,int> > p;
FORE(i,0,n)p.push_back(make_pair(tone[i],duration[i]));
sort(all(p));
int ret=0;
FORE(i,0,n)FORE(j,i,n){
vector<int> vx;
for(int k=i;k<=j;k++)vx.push_back(p[k].second);
sort(all(vx));
int tt=T-(p[j].first-p[i].first);
for(int k=0;k<vx.size();k++){
tt-=vx[k];
if(tt<0)break;
ret=max(ret,k+1);
}
}
return ret;
}
};
public: int maxSongs(vector<int> duration, vector<int> tone, int T) {
int n=duration.size();
vector<pair<int,int> > p;
FORE(i,0,n)p.push_back(make_pair(tone[i],duration[i]));
sort(all(p));
int ret=0;
FORE(i,0,n)FORE(j,i,n){
vector<int> vx;
for(int k=i;k<=j;k++)vx.push_back(p[k].second);
sort(all(vx));
int tt=T-(p[j].first-p[i].first);
for(int k=0;k<vx.size();k++){
tt-=vx[k];
if(tt<0)break;
ret=max(ret,k+1);
}
}
return ret;
}
};