Reversi
typeryougishiki
2019-07-15 20:34:38
### 思路：
大概算DP，从第N个往前遍历，统计i..n区间内的可能性数量f[i]
如果i和i+1的颜色相同，则f[i] = f[i+1]
否则f[i] = f[i+1]+{f[j+1]|color[i]==color[j]&&color[j]!=color[j+1]}
需要在向前遍历的时候记录每个颜色的石头下一个石头（颜色不一样的情况下）开头的区间情况数sit[c],就有f[i] = f[i+1] + sit[color[i]],复杂度降到O(n)
### 代码：
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
#include<map>
#include<cstring>
#include<string>
#include<array>
#include<set>
#include<map>
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
int ss[200001] = {};
int rec1[200010] = {};
vector<int> rec2[200010];
ll rec3[200010] = {};
ll rec4[200010] = {};
int main() {
//freopen("test.txt","r",stdin);
int n;
cin >> n;
for (size_t i = 1; i <= n; i++)
{
scanf("%d", &ss[i]);
rec1[i] = rec2[ss[i]].size();
rec2[ss[i]].push_back(i);
}
rec4[ss[n]] = 1;
rec3[n] = 1;
for (int i = n - 1; i >= 1; i--) {
rec3[i] += rec3[i + 1];
if (ss[i] == ss[i+1])
{
continue;
}
int j = rec1[i]+1;
rec3[i] += rec4[ss[i]];
rec3[i] %= 1000000007;
if (ss[i] != ss[i + 1]) {
rec4[ss[i]] += rec3[i + 1];
rec4[ss[i]] %= 1000000007;
}
}
cout << rec3[1] << endl;
return 0;
}
```