2021.10.08pm

10.08PM

预期 实际
A 100 100
B 100 100
C 100 100
S 300 300

当我AK了,不能说明我强,只能说题出的菜

A[SCOI2009] 生日快乐 \(\blacktriangle\)

  1. 一个非常悲伤的故事:搜索比记忆化搜索快。所以,摆烂了。

B[SCOI2009] 最长距离 \(\blacktriangle\)

  1. 今天的题属于全是暴力了。
  2. 这道题难在建模,从一个点到另一个点能不搬石头最好,需要搬则肯定想的是搬的越少越好,那不就是最短路嘛!只不过边权变成了点权。
  3. 显然 \(floyd\) 要T。不过按照李某的说法 \(floyd\) 不如跑n次\(Dijkstra\)出题人还是太拉了

C[SCOI2009] windy数 \(\blacktriangle\!\blacktriangledown\)

  1. 第一道数位DP属于是。
  2. 看一趟下来就我的状态设置的最离谱。
  3. \(DP[i][j]\) 表示到第 \(i\) 位,数字为 \(j\) 的方案数。
  4. 初始状态:\(DP[head][1\le j\le ch[head]]=1\)
  5. 由于可以以某一位开头,所以说对于每个\(DP[i][j>0]\)都初始化为1。
  6. 转移方程:\(DP[i][j]=\sum DP[i-1][k],|k-j|\ge 2\)
  7. 对于 \(j>ch[i]且k=ch[i-1]且ch[i-1]符合规则时\),\(DP[i][j]-=1\)

2021.10.08pm

\(\cal {Made} \ {by} \ {YuGe}\)

上一篇:BZOJ1026: [SCOI2009]windy数(数位dp)


下一篇:P2564 [SCOI2009]生日礼物