枚举在那个咖啡店喝咖啡

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

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

前缀和+后缀和

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

f [ i ] [ j ] = f [ i 1 ] [ j ] + ( c o l o r [ i ] = = j ) f[i][j]=f[i-1][j]+(color[i]==j) f[i][j]=f[i1][j]+(color[i]==j)

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

g [ i ] [ j ] = g [ i + 1 ] [ j ] + ( c o l o r [ i ] = = j ) g[i][j]=g[i+1][j]+(color[i]==j) g[i][j]=g[i+1][j]+(color[i]==j)

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

s i g m a ( f [ i 1 ] [ j ] g [ i + 1 ] [ j ] ) + f [ i 1 ] [ x ] + g [ i + 1 ] [ x ] sigma( f[i-1][j]*g[i+1][j] )+f[i-1][x]+g[i+1][x] sigma(f[i1][j]g[i+1][j])+f[i1][x]+g[i+1][x]