CF17_FINAL D. Zabuton
Difficulty:2509
問題文
#CF17_F #CF1
#EDPC-X #全順序 #DP
#解説AC
問題
体力Hと力Pが定められたN人の人がいる。
はじめ、高さは0である。人は、高さがH以下であるとき、高さをP上げる操作ができる。
適切に人を並び替えたとき、最大何人が操作できるか。
解法
#EDPC-X そのものすぎる。H+Pが小さい順にソートして、あとは普通にDPするだけ
実装
提出コード
code:cpp
bool solve(){
LL(n);
vector<tuple<ll,ll,ll>>v(n);
rep(i,n){
LL(h,p);
vi = {h+p,h,p};
}
sort(ALL(v));
vector dp(n+1,INF);
dp0 = 0;
ll ans{};
rep(i,n){
vector ndp = dp;
if(dp.back()!=INF){
O(n);
return false;
}
auto_,h,p = vi;
rep(j,n){
if(dpj<=h){
chmin(ndpj+1,dpj+p);
}
}
swap(dp,ndp);
}
rep(i,n+1)if(dpi<INF)chmax(ans,i);
O(ans);
return false;
}