【题目记录】AtCoder - agc031 B

你的名字 2022-10-15 00:39 60阅读 0赞

题目链接 [AtCoder - agc031 B][]

题意: 有一个长度为N的颜色序列，第i个位置初始颜色为 C i C\_i Ci, 可以执行若干次操作，每次选择两个颜色一样的石头，然后把这两个位置中间的区间都刷成和两端相同的颜色，问最后不同的颜色序列有多少种。

不需要考虑操作的过程如何，只要考虑最后的颜色序列，假设 \[ l 1 , r 1 \] \[l\_1,r\_1\] \[l1,r1\]和 \[ l 2 , r 2 \] \[l\_2,r\_2\] \[l2,r2\]分别是先后两次操作。

若前者和后者相交但不包含，若前后两次刷成的颜色相同，我们可以等效成一次操作，操作区间为它们的并。  
若前后两次颜色不同，那么这种情况一定是不存在的，因为相交但不包含意味着第一个区间的一个端点在第二个区间里，那这个端点在执行完前面的操作之后就不再是颜色2而变成颜色1了。

若前者包含后者，则后者无用。  
若后者包含前者，则前者无用。

若两次区间不相交，则两次都有用。

所以本题就是要求把长度为N的序列内取出若干不相交区间，每个区间两端点颜色相同的方案数。

我们先对序列进行如下处理: 把所有连续的颜色相同的区间缩成一个位置。例如122333441变成12341.

然后 f i f\_i fi表示前i个的方案数。  
 f i = Σ j ≤ i , a j = a i f j − 1 f\_i=\\Sigma\{\_\{j≤i,a\_j=a\_i\}f\_j−1\} fi=Σj≤i,aj=aifj−1  
主要是考察DP计数方面的内容  
时间复杂度O(n).

#include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #define llong long long
    using namespace std;
    
    const int N = 2e5;
    const int P = 1e9+7;
    int a[N+3],b[N+3];
    llong f[N+3],g[N+3];
    int n;
    
    int main()
    {
    	scanf("%d",&n);
    	for(int i=1; i<=n; i++) scanf("%d",&a[i]);
    	int m = 0; for(int i=1; i<=n; i++) if(i==0 || a[i]!=a[i-1]) {m++; b[m] = a[i];}
    	n = m; for(int i=1; i<=n; i++) a[i] = b[i];
    	f[0] = 1ll; g[a[1]] = 1ll;
    	for(int i=1; i<=n; i++)
    	{
    		f[i] = g[a[i]];
    		g[a[i+1]] = (g[a[i+1]]+f[i])%P;
    	}
    	printf("%lld\n",f[n]);
    	return 0;
    }

[AtCoder - agc031 B]: https://atcoder.jp/contests/agc031/tasks/agc031_b?lang=en