如果咖啡店不同也算作不同的方案,那显然是枚举咖啡店,然后记录两侧每种颜色的客栈实时更新。
但算作相同的方案反而有点巧妙了,按编号从小到大枚举,记录当前花费可行的编号最大的咖啡店 (mx) 和每种颜色的客栈上一次的出现位置 (a_i),再维护每种颜色的客栈在 (mx) 之前的数量 (f_i)。
当 (mxgeq a_i) 时,显然之前所有对应颜色的客栈都能与当前客栈匹配,更新 (f_i)。这一步其实就是计算 (i) 作为咖啡店的贡献并替换掉上一个肯定不优的贡献。
否则 (f_i) 一定是更新完全的,因为之前每个花费可行的咖啡店都能更新完全。
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 20005
#define For(i,x,y)for(i=x;i<=(y);i++)
int a[N],b[N],f[N];
int read()
{
int A;
bool K;
char C;
C=A=K=0;
while(C<'0'||C>'9')K|=C=='-',C=getchar();
while(C>'/'&&C<':')A=(A<<3)+(A<<1)+(C^48),C=getchar();
return(K?-A:A);
}
int main()
{
ll s=0;
int n,k,p,i,mx,w,col;
n=read(),k=read(),p=read();
For(i,1,n)
{
col=read(),w=read();
if(w<=p)mx=i;
if(mx>=a[col])f[col]=b[col];
a[col]=i;
s+=f[col];
b[col]++;
}
cout<<s;
return 0;
}