题意简述：现在要选两个客栈出来，这两个客栈满足两个条件：1.颜色相同 2.中间有一家咖啡馆/客栈价格低于P（包括他们本身）。
思路：由于这道题只是问有几种选择客栈的情况，而不是选两个客栈与一个咖啡馆。换句话说，只要这两个客栈中间有咖啡馆就行了，至于到底是哪个不重要。开始枚举客栈，我们记录对于当前客栈来讲最近的可选咖啡馆（如果自己的咖啡馆可选那就是自己，不然就继承），并且动态记录一下在这个咖啡馆前面各个颜色的客栈数量。由于是在这个咖啡馆前面，所以也满足咖啡馆在两个客栈中间的要求，颜色相同，答案直接加记录的相同颜色客栈数就行了。
代码
#include<iostream> #include<cstdio> #include<fstream> #include<cmath> #include<algorithm> #include<cstring> using namespace std; int read(){ char ch; int res=0,f=1; ch=getchar(); while(ch<‘0‘||ch>‘9‘){ if(ch==‘-‘)f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘){ res=res*10+(ch-‘0‘); ch=getchar(); } return res*f; } const int MAXN=200005; int n,k,p,ans,now; int cnt[51],f[MAXN],color[MAXN]; int main(){ n=read();k=read();p=read(); for(int i=1;i<=n;++i){ int a,b; a=read();b=read(); color[i]=a; if(b<=p){ for(int j=i;j>now;--j)cnt[color[j]]++; now=i; ans+=cnt[a]-1;//不与自己组成一对客栈 } else ans+=cnt[a]; } cout<<ans; return 0; }
原文：https://www.cnblogs.com/clockwhite/p/11567021.html
