AtCoder Grand Contest 031 B

https://atcoder.jp/contests/agc031/tasks/agc031_b

B - Reversi

Time Limit: 2 sec / Memory Limit: 1024 MB

Problem Statement

There are $N$ stones arranged in a row. The $i$ -th stone from the left is painted in the color $C_{i}$ .

Snuke will perform the following operation zero or more times:

Choose two stones painted in the same color. Repaint all the stones between them, with the color of the chosen stones.

Find the number of possible final sequences of colors of the stones, modulo $10^{9} + 7$ .

Constraints

$1 \leq N \leq 2 \times 10^{5}$
$1 \leq C_{i} \leq 2 \times 10^{5} (1 \leq i \leq N)$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

 $N$ 
 $C_{1}$ 
 $:$ 
 $C_{N}$

Output

Print the number of possible final sequences of colors of the stones, modulo 1e9+7.

题意：有N个有颜色的石头，你可以选择两个颜色相同的石头使他们之间的石头颜色全部变成他们的颜色，重复这个操作任意次(可以为0次)，问共有多少种情况

题解：DP.在N-1个石头的方案数dp[N-1]上面考虑第N个石头对结果的贡献，可以得到-->贡献==第N块石头与前面与他颜色相同的石头进行操作的总可能数，可以想到这个可能数==离他最近的与他颜色相同的石头q的总方案数dp[q]，因为第N块石头连向更远的石头都可以看成是先连向离他最近的石头之后再向前连接,所以状态方程就是dp[i]=dp[i-1]+dp[q]，其中q是离i最近的与他颜色相同的石头的编号.

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<vector>
 5 using namespace std;
 6 typedef long long ll;
 7 const ll mod=1e9+7;
 8 int a[200005],c[200005],b[200005];
 9 ll dp[200005];
10 int main(){
11     int n,m;
12     cin>>n;
13     for(int i=1;i<=n;i++){scanf("%d",&a[i]);}
14     c[1]=a[1];
15     int tot=1;
16     for(int i=2;i<=n;i++){
17         if(a[i]!=c[tot])c[++tot]=a[i];
18     }
19     dp[0]=1;
20     for(int i=1;i<=tot;i++){
21         if(b[c[i]])dp[i]=(dp[i-1]+dp[b[c[i]]])%mod;
22         else dp[i]=dp[i-1];
23         dp[i]%=mod;
24         b[c[i]]=i;
25     }
26     cout<<dp[tot]<<endl;
27     return 0;
28 }

View Code