$f[i]$表示$i..n$能取到的最大和
$g[i]$表示$i..n$取到最大和时,最先取到的点
从后往前跑,对于一个点,考虑它取不取
如果不取,$f[i]=f[i+1],g[i]=g[i+1]$
如果取,$f[i]=f[g[i+1]+1]+a[i],g[i]=i$
因为$g[i+1]$表示$i+1$取最大和时,最先取到的点,如果取i,那么下一头牛就会取$i+1..n$的最大和,也就是取第$g[i+1]$个。那么当前这头牛就只能从$g[i+1]+1$开始取,所以是$f[i]=f[g[i+1]+1]+a[i]$
code
1 |
|