听说这道题是当年省选题

于是兴致勃勃拿来做了做

至于如何想到思路...

事实上没想象中那么简单...

脑阔挺疼的...

(一开始都没看出来是区间dp)

想到可以区间dp，然后就似乎没啥大问题

枚举区间dp[i][j]的时候，如果i j一样那就好说，相当于当初某一次涂的时候多往外涂一格就好

如果i j不一样？我反而在这里懵了

但我误打误撞就给正解写出来了

想不到正解居然这么简单？？？

认真思考之后大体明白了

因为不能像i==j那样直接多涂一个

所以就可以直接区间枚举了...

总有一个是最优的

 

1 #include
     
       2 int min(int a,int b){
   return a
     

以上，有点后悔出生太晚了

2018NOIP简直毒瘤啊

(NOIP=POI*N)

再看看当年省选...

 

做完这道题之后你可以再去看看

没错他们完全一样