洛谷 P1311 【选择客栈】

枚举在那个咖啡店喝咖啡

想要计算咖啡店两侧同色的客栈的对数

枚举i求和（左边第i种颜色的个数*右边第i种颜色的个数）

前缀和+后缀和

$f\left[i\right]\left[j\right]$f[i][j]表示到第i家客栈及之前颜色为j的客栈有几个

$f\left[i\right]\left[j\right]=f[i-1]\left[j\right]+\left(color\right[i]==j)$f[i][j]=f[i−1][j]+(color[i]==j)

$g\left[i\right]\left[j\right]$g[i][j] 表示到第i家客栈及之后颜色为j的客栈有几个

$g\left[i\right]\left[j\right]=g[i+1]\left[j\right]+\left(color\right[i]==j)$g[i][j]=g[i+1][j]+(color[i]==j)

假设当前客栈咖啡店消费<=p 当前位置为i 颜色为x

$sigma\left(f\right[i-1\left]\right[j]\ast g[i+1\left]\right[j\left]\right)+f[i-1]\left[x\right]+g[i+1]\left[x\right]$sigma(f[i−1][j]∗g[i+1][j])+f[i−1][x]+g[i+1][x]