Mirror的演算法筆記

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=b231 這題同 https://mirrorshih.blogspot.com/2019/07/tioj-1072-a.html 這題一樣 以下為code #include < bits/stdc++.h > using namespace std; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ),cout. tie ( 0 ); int main () { AC ll n,r = 0 ,t = 0 ; cin >> n; priority_queue < pair < ll,ll >> pq; for (ll i = 0 ;i < n;i ++ ) { ll t1,t2; cin >> t1 >> t2; pq. push ({t2,t1}); } for (;pq. size ();pq. pop ()) { t += pq. top ().second; r = max (r,t + pq. top ().first); } cout << r << ' \n ' ; }

呃... 沒有證明隨便亂寫就AC了 題目鏈接: https://tioj.ck.tp.edu.tw/problems/1072 總之就是用Greedy跑下去就對啦 從吃最久的人先開始跑 把每道菜所需做的時間都存下來 (因為就算每個人都吃零分鐘也需要消耗做菜時間) 也就是說所需最小時間≥做菜時間 每次做完一道新菜後,再比較當前所用做菜時間加上吃飯時間(R)和之前所用最大的R 取其中大者 (也就是吃飯時間有沒有超過做下一道菜的時間) 以下為code #include < bits/stdc++.h > using namespace std; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ),cout. tie ( 0 ); int main () { AC ll n; while (cin >> n && n) { ll c,e,r = 0 ,t = 0 ; priority_queue < pair < ll,ll >> pq; for (ll i = 0 ;i < n;i ++ ) { cin >> c >> e; pq. push ( make_pair (e,c)); } for (;pq. size ();pq. pop ()) { t += pq. top ().second; r = max (r,t + pq. top ().first); } cout << r << ' \n ' ; } }

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=d887 計算可行的數量,用DP求解 (圖為題目範例中n=3的情況) 可知上坡的數量≥於下坡的數量 於是可畫出上圖 得狀態轉移式為 dp[i][j]=dp[i-1][j]+dp[i][j-1] 以下為code #include < bits/stdc++.h > using namespace std; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ),cout. tie ( 0 ); int main () { AC ll n,dp[ 26 ][ 26 ]; memset (dp, 0 , sizeof (dp)); fill (dp[ 0 ],dp[ 0 ] + 26 , 1 ); for (ll i = 1 ;i < 26 ;i ++ ) for (ll j = i;j < 26 ;j ++ ) dp[i][j] = dp[i - 1 ][j] + dp[i][j - 1 ]; while (cin >> n) cout << dp[n][n] << ' \n ' ; } 要是沒看過這種推上下坡的寫法完全想不出答案... DP也太難了吧 還有這次又被忘記初始化陣列給卡住了 下次還要注意一點

題目鏈接: https://tioj.ck.tp.edu.tw/problems/1291 可知放m球的可能性可從m-1球推得 用DP求解 得轉移曲線為 dp[i][j]=dp[i][j-1]*i+dp[i-1][j-1] 放i箱j-1球加一球可以放在箱子的任何位置,也就是i種可能性 但也有可能前j-1球只放在前i-1箱中,則第j球獨立放在一箱 以下為code #include < bits/stdc++.h > using namespace std; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ),cout. tie ( 0 ); int main () { AC ll n,m,dp[ 201 ][ 201 ]; memset (dp, 0 , sizeof (dp)); dp[ 0 ][ 0 ] = 1 ; for (ll i = 1 ;i < 201 ;i ++ ) for (ll j = 1 ;j < 201 ;j ++ ) dp[i][j] = (dp[i][j - 1 ] * i + dp[i - 1 ][j - 1 ]) % 1000000 ; while (cin >> n >> m && n && m) { ll r = 0 ; for (ll i = 1 ;i <= n;i ++ ) r = (r + dp[i][m]) % 1000000 ; cout << r << ' \n ' ; } } 要特別注意的是寫dp題目時要設定好初始值,否則會引發特殊情況導致WA,我在這裡卡超久... 還有就是%的運算優先級順序也要特別注意