10.08PM
预期 | 实际 | |
---|---|---|
A | 100 | 100 |
B | 100 | 100 |
C | 100 | 100 |
S | 300 | 300 |
当我AK了,不能说明我强,只能说题出的菜
A[SCOI2009] 生日快乐 \(\blacktriangle\)
- 一个非常悲伤的故事:搜索比记忆化搜索快。所以,摆烂了。
B[SCOI2009] 最长距离 \(\blacktriangle\)
- 今天的题属于全是暴力了。
- 这道题难在建模,从一个点到另一个点能不搬石头最好,需要搬则肯定想的是搬的越少越好,那不就是最短路嘛!只不过边权变成了点权。
- 显然 \(floyd\) 要T。不过按照李某的说法 \(floyd\) 不如跑n次\(Dijkstra\),
出题人还是太拉了。
C[SCOI2009] windy数 \(\blacktriangle\!\blacktriangledown\)
- 第一道数位DP属于是。
- 看一趟下来就我的状态设置的最离谱。
- \(DP[i][j]\) 表示到第 \(i\) 位,数字为 \(j\) 的方案数。
- 初始状态:\(DP[head][1\le j\le ch[head]]=1\)
- 由于可以以某一位开头,所以说对于每个\(DP[i][j>0]\)都初始化为1。
- 转移方程:\(DP[i][j]=\sum DP[i-1][k],|k-j|\ge 2\)
- 对于 \(j>ch[i]且k=ch[i-1]且ch[i-1]符合规则时\),\(DP[i][j]-=1\)
\(\cal {Made} \ {by} \ {YuGe}\)