P6032 选择客栈 加强版 递推

P6032 选择客栈 加强版

​ 题目链接

​

​ 递推。

​

​ 其实思路挺难想的，但代码好打。

​ (last[x])表示(x)这个颜色上一次出现的位置。

​ (cnt[x])表示(x)这个颜色出现的次数。

​ (sum[x])相当于一个寄存器，实时更新(x)颜色的答案。

​ 思路就是枚举第二个客栈，第二个客栈的颜色假设为(x)，(now)记录的是离当前第(x)个客栈最近的可以喝咖啡的地方，如果说这个地方大于等于(last[x])，那么当前枚举到的客栈可以与之前所有颜色为(x)的客栈组成合法方案，那么此时就更新(sum[x] = cnt[x]，cnt[x] ++)，注意顺序不能反。

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

const int N = 2e6 + 100;
int n, k, p;
int sum[10005], cut[10005], last[10005];
long long ans;

int main() {
	scanf("%d %d %d", &n, &k, &p);
	for(int i = 1, x, y, now;i <= n; i++) {
		scanf("%d %d", &x, &y);
		if(y <= p) now = i;
		if(now >= last[x]) sum[x] = cut[x];
		cut[x]++; last[x] = i;
		ans += sum[x];
	}
	printf("%lld", ans);
	
}