题面:https://www.luogu.com.cn/problem/P1311
丽江河边有 nn 家很有特色的客栈，客栈按照其位置顺序从 11 到 nn 编号。每家客栈都按照某一种色调进行装饰（总共 kk 种，用整数 0 \sim k-10∼k−1 表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。
两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过 pp 。
他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过 pp 元的咖啡店小聚。
样例:
5 2 3 0 5 1 3 0 2 1 4 1 5
写出这题还是比较得意的，虽然中途下载了测试数据，不过思想是自己的。
①自己的思想O(nk)
Ⅰ.我们这样想，如果一个客栈的右边(包括自己)都是花费大于P的，那么这个客栈的右边一定不存在和这个客栈匹配的。
Ⅱ.如果某个客栈 i 和右边的同色客栈 j 符合条件的话，那么他们之间肯定存在一个花费低于P的客栈
Ⅲ.在Ⅱ的基础上， j 右边的同色客栈一定能和i组成符合条件的。
Ⅳ.综上所诉，我们只关系客栈右边第一个价值符合条件的客栈位置，以及该符合条件的客栈(包括该客栈)右边有几个同色客栈。
②实现
Ⅰ.客栈右边第一个价值低于P客栈的位置，我们直接倒序枚举。
初始令ans=-1表示右边没有合适的客栈了
然后发现一个符合条件的客栈就更新ans的位置
int ans=-1;//表示没有 for(int i=n;i>=1;i--) { if(hua[i]<=p) ans=i;//更新 jin[i]=ans; }
Ⅱ.对于颜色统计，仍然倒序枚举，用vis数组统计颜色情况。
sumn [ i ] [ j ] 表示在 i 客栈后面(包括 i 客栈)有 j 颜色的客栈多少个
for(int i=n;i>=1;i--) { vis[color[i]]++;//统计当前颜色 for(int j=0;j<=k;j++) sumn[i][j]=vis[j];//把所有颜色装进去 }
代码如下
#include <bits/stdc++.h> using namespace std; const int maxn=200009; int n,k,p; int color[maxn],hua[maxn],vis[59]; int jin[maxn];//从i往后,最快遇到得廉价酒馆 int sumn[maxn][59];//从i往后，不包括i与i同色得酒馆 int main() { scanf("%d%d%d",&n,&k,&p); for(int i=1;i<=n;i++) scanf("%d%d",&color[i],&hua[i]); int ans=-1; for(int i=n;i>=1;i--) { if(hua[i]<=p) ans=i; jin[i]=ans; vis[color[i]]++; for(int j=0;j<=k;j++) sumn[i][j]=vis[j]; } int cnt=0; for(int i=1;i<=n;i++)//O(n)扫一遍 { if(jin[i]==-1) continue; //右边没有价值更低的客栈了,continue cnt+=sumn[jin[i]][color[i]]; if(jin[i]==i) cnt--; //如果自己就是距离最近的廉价客栈 //那么sumn[jin[i]][color[i]]多算了一次 //自己是不可以和自己匹配的 } cout<<cnt; }
不过，令人伤心的是，还有更快的O（n）算法。
箭头代表该客栈是小于花费P的客栈
那么，当我们枚举到第二个客栈时，发现这是在当前枚举过程中最后出现的一个符合花费的客栈，我们把他的下标记作 t
所以后面的客栈总可以和第二个客栈前面的同色客栈形成一对
然后我们枚举到第四个客栈时，更新t
从第四个客栈开始起，所有后续客栈都可以和4之前的同色客栈形成一对,而不是仅仅和2之前的同色客栈形成一对。
所以奉上代码:
#include <bits/stdc++.h> using namespace std; const int maxn=500009; int n,k,p,last[maxn],sumn[maxn]; int color,price,vis[59]; //vis记录颜色 int main() { cin>>n>>k>>p; int ans=0,now; for(int i=1;i<=n;i++) { cin>>color>>price; if(price<=p) now=i; //now记录目前最后符合条件的客栈编号 if(now>=last[color])//如果大于上一个颜色出现的位置 sumn[color]=vis[color];//那么不仅仅是2之前的，现在是4之前的 last[color]=i;//最后一次出现在i ans+=sumn[color]; vis[color]++; } cout<<ans; }
原文：https://www.cnblogs.com/iss-ue/p/12494740.html
