AtCoder Beginner Contest 285 成绩报告
\(AC:T1,\ T2,\ T3,\ T4\quad 1000pts\)
\(rk2122,\ +59\)
P1280 尼克的任务
这道题标签是 \(DP\) ，但是按照标签写题显得没有挑战性，于是另辟蹊径把 \(DP\) 转化成图上问题。建图思路：
- 把每一分钟看做图上一个节点
- 对于时间为 \(t1-t2\) 的一份工作，在 \(t1\) 和 \(t2\) 之间连一条长度为 \(t2-t1\) 的边（这里 \(t2\) 指的是工作完成以后的第一分钟，即 \(p+t\) ，而非题目中说的 \(p+t-1\)）
- 进行完上面操作后，对于有入度而没有出度的节点，向大于它且有出度的节点或 \(n+1\) 连一条长度为 \(0\) 的边
图建好后以1为起点跑 \(SPFA\) 即可，平均复杂度 \(O(kn)\) ，其中 \(k \approx 2\) .
P3045 Cow Coupons G
首次学习可悔贪心，自认为不难，比较容易理解，题目也像是模板的感觉
P8940 不见故人
很巧妙的贪心，又是赛时想不出，知道正解恍然大悟的题目
P2158 仪仗队
类似P1447 能量采集的一道题，代码10行，主要难在思维。关键是想到满足题意的点需要 \(gcd(x,\ y)=1\) ，以及快速求 \(gcd\) 的办法
UVA10820 Send a Table
上面这题的双倍经验，只是多组输入
P1220 关路灯（最优解）
\(16\) 个最优解祭
区间 \(DP\) 好题，最难的部分是状态的选择而非状态转移方程的推理。实际上题目中并没有给出道路长度的取值范围这一失误反而提醒我状态的设计与路灯位置无关，于是设计出 \(dp[i][j][0/1]\) ，其中 \(dp[i][j][0]\) 表示关掉 \(i\) 到 \(j\) 的灯以后，人位于 \(i\) 处； \(dp[i][j][1]\) 表示关掉 \(i\) 到 \(j\) 的灯以后，人位于 \(j\) 处。状态转移方程很自然就推出来了：
\(f[i][j][0]=min(f[i+1][j][0]+(a[i+1]-a[i])*(sum[i]+sum[n]-sum[j]),f[i+1][j][1]+(a[j]-a[i])*(sum[i]+sum[n]-sum[j]))\)
\(f[i][j][1]=min(f[i][j-1][0]+(a[j]-a[i])*(sum[i-1]+sum[n]-sum[j-1]),f[i][j-1][1]+(a[j]-a[j-1])*(sum[i-1]+sum[n]-sum[j-1]))\)