早安 ?
昨晚比 codechef starters 太晚睡了今天没什么精神。打算写完这篇去补眠zzz
习题
dp什么都不会所以就练了一点
1472B Fair Division
| Rating | Tags |
|---|---|
| 800 | dp, greedy |
一开始想不到如何套dp进这题，就打个纯贪心拿了 AC
然后是看到这个评论才明白dp的做法
首先还是先要将 $a$ 逆序排列
| 状态表示 | $dp[i]$ 表示以 $a[i]$ 为结尾 Alice 和 Bob 糖果数量的最小差 |
|---|---|
| 转移方程 | $dp[i]=|dp[i-1]-a[i]|$ |
| 边界 | $dp[0]=a[0]$ |
| 目标 | $dp[n-1]\stackrel{?}{=}0$ |
时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)
702A Maximum Increase
| Rating | Tags |
|---|---|
| 800 | dp |
经典 Longest Increasing Subarray 问题
| 状态表示 | $dp[i]$ 表示以 $a[i]$ 为结尾的上升子数组的长度 |
|---|---|
| 转移方程 | $dp[i]=\begin{cases} dp[i-1]+1 & : \text{if } a[i]>a[i-1] \\ 1 & : \text{otherwise} \end{cases}$ |
| 边界 | $dp[0]=1$ |
| 目标 | $\max\limits_{0{\leq}i<n}\{dp[i]\}$ |
时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)
1538A Stone Game
| Rating | Tags |
|---|---|
| 800 | brute force, greedy |
实在想不到什么dp的做法，网上找也没有。只好打了个贪心AC
时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)
489B BerSU Ball
| Rating | Tags |
|---|---|
| 1200 | dp |
一开始想的转移方程就错了，还不小心写了个双指针出来？?
之后参考了这个
| 状态表示 | $dp[i][j]$ 表示前缀子串 $a[0...i-1]$ 和 $b[0...j-1]$ 里成对的最大数量 |
|---|---|
| 转移方程 | $dp[i][j]=\max\{dp[i-1][j-1]+|a[i-1]-b[j-1]|{\le}1,dp[i][j-1],dp[i-1][j]\}$ |
| 边界 | $dp[i][0]=0,dp[0][j]=0,0{\le}i{\le}n,0{\le}j{\le}m$ |
| 目标 | $dp[n][m]$ |
时间复杂度：\(O(nm)\)
空间复杂度：\(O(nm)\)
比赛
CodeChef Starters 114C
| Solved | Rank | Score | New Rating | Old Rating | ∆ |
|---|---|---|---|---|---|
| 3/8 | 233 | 350 | 1604 | 1419 | +185 |
在 clist 上看到有比赛就来了
2230-0045实在太夜了一直想睡觉zzzz
A 和 B 一开始轻松解决
看了 C 和 D 后觉得 C 没有头绪而去做 D
没想到居然误解了题目拿 WA ，当时还以为又没开 long long（前一天 binary search 的教训）
之后发现是 IOI 赛制（答错没有 penalty）所以大胆用贪心幸运 AC 了 C
多亏 D 有 N is odd 的 subtask 苟且拿到 50 分
最后如愿以偿 (?) 上了 3 Stars ?
小结
第一篇记录yay!
光是 \(\LaTeX\) 都用了我半小时?
之后的记录要简洁一些了?
今天的目标： Codeforces Div4 上 specialist ? 用CF Calc算了算，还是慢慢打比赛吧?