丽江河边有 n 家很有特色的客栈，客栈按照其位置顺序从 1 到 n 编号。每家客栈都按照某一种色调进行装饰（总共 k 种，用整数 0 ~ k-1 表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。 两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过 p 。 他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过 p 元的咖啡店小聚。

这是一道算法问题，我可以回答。我们可以用双指针法来解决这个问题。首先，我们将客栈按照色调进行分类，得到 k 个客栈集合。对于每个客栈集合，我们分别用双指针法来找到两个客栈，使得它们之间的咖啡店最低消费不超过 p 。具体地，我们用两个指针 i 和 j 分别指向客栈集合中的第一个和最后一个客栈，然后不断地移动指针，直到找到一对客栈，它们之间的咖啡店最低消费不超过 p 。此时，我们可以计算出在这个客栈集合中选择两个客栈的方案数，然后将所有客栈集合的方案数相加即可得到总方案数。时间复杂度为 O(kn)。

相关问题

使用C++实现：丽江河边有 n 家很有特色的客栈，客栈按照其位置顺序从 1 到 n 编号。每家客栈都按照某一种色调进行装饰（总共 k 种，用整数 0 ~ k-1 表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。 两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过 p 。 他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过 p 元的咖啡店小聚。

这是一个算法问题，可以使用 C 语言实现。具体实现方法是，先将客栈按照色调分类，然后对于每一种色调，找到其中最靠前和最靠后的两家客栈，分别记为 l 和 r。接下来，枚举两位游客住宿的客栈编号 i 和 j，满足 i < j 且 i 和 j 分别属于两种不同的色调。然后再枚举咖啡店的位置 k，满足 l <= k <= r 且咖啡店的最低消费不超过 p。最后，将所有符合条件的方案数累加起来即可。

具体实现代码如下：

int cnt = ;
for (int c1 = ; c1 < k; c1++) {
for (int c2 = c1 + 1; c2 < k; c2++) {
int l1 = -1, r1 = -1, l2 = -1, r2 = -1;
for (int i = ; i < n; i++) {
if (color[i] == c1) {
if (l1 == -1) l1 = i;
r1 = i;
}
if (color[i] == c2) {
if (l2 == -1) l2 = i;
r2 = i;
}
}
for (int i = l1; i <= r1; i++) {
for (int j = l2; j <= r2; j++) {
if (i < j) {
for (int k = i; k <= j; k++) {
if (cafe[k] <= p) {
cnt++;
break;
}
}
}
}
}
}
}
printf("%d\n", cnt);

注意，这里的 color 数组表示每家客栈的色调，cafe 数组表示每家咖啡店的最低消费。

使用C++实现代码：丽江河边有 n 家很有特色的客栈，客栈按照其位置顺序从 1 到 n 编号。每家客栈都按照某一种色调进行装饰（总共 k 种，用整数 0 ~ k-1 表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。 两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过 p 。 他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过 p 元的咖啡店小聚。

我可以回答这个问题。这个问题可以使用动态规划来解决。定义一个二维数组 dp[i][j] 表示游客住在第 i 家客栈，另一个游客住在第 j 家客栈，且两家客栈之间有一家咖啡店的最低消费不超过 p 的方案数。初始状态为 dp[i][j]=1，当 i=j 时，dp[i][j]=。转移方程为 dp[i][j]=sum(dp[i-1][k])，其中 k 满足 k<j 且第 k 家客栈到第 j 家客栈之间有一家咖啡店的最低消费不超过 p。最终答案为 sum(dp[i][j])，其中 i<j。时间复杂度为 O(n^3)。