AtCoder Grand Contest 031 B Reversi dp

Description

有n個磚頭(?)，每個磚頭有自己的顔色。我們每次可以選擇兩個顔色相同的磚頭然後把它們之間的磚頭都染成這種顔色，問任意操作之後最終不同的結果有多少種

Solution

腦子不夠用，來寫一點日本題

我們把一次操作看成選取一個區間，那麼最終序列不同等價于選擇的區間不同

兩個區間的關系讨論一下就有

A包含B，那麼隻有一個有用

A與B相離，那麼A和B都可以選

A與B香蕉，那麼隻有一個有用

很顯然，我們最終選出來的區間一定是一堆不相交的、端點顔色相同的區間，這個dp就可以了

Code

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <math.h>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define fill(x,t) memset(x,t,sizeof(x))

typedef long long LL;
const int MOD=1000000007;
const int N=2000005;

int f[N],s[N],a[N],b[N];

int read() {
	int x=0,v=1; char ch=getchar();
	for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
	for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
	return x*v;
}

int main(void) {
	int n; scanf("%d",&n);
	rep(i,1,n) scanf("%d",&a[i]);
	for (int i=1,j;i<=n;) {
		j=i;
		while (a[j]==a[j+1]) j++;
		b[++b[0]]=a[j];
		i=j+1;
	}
	f[0]=1;
	s[b[1]]=1;
	rep(i,1,b[0]) {
		f[i]=s[b[i]];
		s[b[i+1]]=(s[b[i+1]]+f[i])%MOD;
	}
	printf("%d\n", f[b[0]]);
	return 0;
}