SRM 588 div2
初するめ。
250 KeyDungeonDiv2
鍵は消え去らないので普通に左から見ていく。
足りない分は白鍵で補充してやる。
class KeyDungeonDiv2 { public: int countDoors(vector <int> doorR, vector <int> doorG, vector <int> keys) { int n = sz(doorR) ; int ret = 0; rep(i,n){ int redkey = keys[0]; int greenkey = keys[1]; int whitekey = keys[2]; int red = doorR[i],green = doorG[i]; redkey -= red; greenkey -= green; if(redkey >= 0 && greenkey >= 0){ ret++;continue; } int a = 0; if(redkey < 0)a -= redkey; if(greenkey < 0)a -= greenkey; if(whitekey >= a)ret++; } return ret; } };
500 GUMIAndSongsDiv2
区間の差を最小限に抑えるには、
toneを基準に歌をソートしてやる。
あとは
dp[今の個数][一個前の歌の添字] = 最短時間
やって、
dp[i][j] <= T のうち 最大の i が答えである。
class GUMIAndSongsDiv2 { public: int maxSongs(vector <int> duration, vector <int> tone, int T) { vector < int > d = duration; int n = sz(d); vector < Pi > v; rep(i,n) v.pb(mp(tone[i],d[i])); sort(ALL(v)); int dp[55][55]; // fr : tone , sc : d rep(i,n+1)rep(j,n)dp[i][j] = INF; rep(i,n)dp[1][i] = v[i].sc; // dp[今の個数][一個前の歌の添字] = 最短時間 reps(i,2,n+1) rep(j,n) rep(k,j) dp[i][j] = min(dp[i][j],dp[i-1][k] + v[j].sc + abs(v[i-1].fr-v[k].fr)); int ret = 0; rep(i,n+1){ rep(j,n){ if(dp[i][j] <= T)ret = max(ret,i); } } return ret; } };
Easyしばらく読み間違えていて、書き直したものの
一個前のデータがhogeって提出してEasy落とした。
medは読まずに終わってしまった。
時間配分と解釈が狂うと怖い。
本番に弱いタイプなので早くSRMに慣れたい。
次回にはmedまでPassしたい。