洛谷 P1311 【选择客栈】
枚举在那个咖啡店喝咖啡
想要计算咖啡店两侧同色的客栈的对数
枚举i求和（左边第i种颜色的个数*右边第i种颜色的个数）
前缀和+后缀和
f[i][j]f[i][j]f[i][j]表示到第i家客栈及之前颜色为j的客栈有几个
f[i][j]=f[i−1][j]+(color[i]==j)f[i][j]=f[i-1][j]+(color[i]==j)f[i][j]=f[i−1][j]+(color[i]==j)
g[i][j]g[i][j]g[i][j] 表示到第i家客栈及之后颜色为j的客栈有几个
g[i][j]=g[i+1][j]+(color[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
sigma(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[i−1][j]∗g[i+1][j])+f[i−1][x]+g[i+1][x]
腾讯成长空间 5981人发布