P6032 选择客栈 加强版

如果咖啡店不同也算作不同的方案，那显然是枚举咖啡店，然后记录两侧每种颜色的客栈实时更新。

但算作相同的方案反而有点巧妙了，按编号从小到大枚举，记录当前花费可行的编号最大的咖啡店 \(mx\) 和每种颜色的客栈上一次的出现位置 \(a_i\)，再维护每种颜色的客栈在 \(mx\) 之前的数量 \(f_i\)。

当 \(mx\geq 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;
}

P6032 选择客栈 加强版

原文：https://www.cnblogs.com/May-2nd/p/14857602.html