调了个闹钟起来写了发T1，看了一下T2，type1 n^2 dp很好写，然后试着推type2，没什么思路，然后回去睡觉，睡醒发现还是不会。