ABC 215 E - Chain Contestant (狀壓DP)

連結

題意：

給出一個隻包括A~J的字元串，定義一種子序列為：在這個子序列中，相同的字元必定連續出現，求出這樣的子序列有多少個。

資料範圍：字元串長度1 <= n <= 1000

分析：

首先我們看題應該能想到用狀壓DP，那麼我們考慮狀态，我們用​

​DP[i][j][k]​

​表示目前狀态i,j表示選取每個字元的狀态，k表示以k字元結尾。

末尾字元相等
dp[i][j][num]+=dp[i-1][j][k];
不同
dp[i][j][num]+=dp[i-1][j-(1<<num)][k];      

ll dp[2][1024][10], n;
string str;
void solve()
{
    cin >> n;
    cin >> str;
    ll flag = 0;
    ll num = str[0] - 'A';
    dp[flag][1 << num][num] = 1;

    for(int i = 1; i < n; i++)
    {
        flag ^= 1;
        for (int j = 0; j < 1024; j ++)
        {
            for(int k = 0; k < 10; k ++)
            {
                if(j & (1 << k)) ///從上個狀态直接遞歸下來 末尾必須是k
                    dp[flag][j][k] = dp[flag ^ 1][j][k];
            }
        }
        num = str[i] - 'A';
        dp[flag][1<<num][num] ++;
        for(int j = 0; j < 1024; j++)
        {
            if(j & (1 << num)) //以j結尾
            {
                for(int k = 0; k < 10; k++)
                {
                    if(k == num) ///與目前結尾一樣，直接加上上層的方案數
                        dp[flag][j][num] += dp[flag ^ 1][j][k];
                    else 
                        dp[flag][j][num] += dp[flag ^ 1][j - (1 << num)][k]; ///不同 那就讓其轉化過來，
                    dp[flag][j][num] %= MOD;
                }
            }
        }
    }
    ll ans = 0;
    for(int j = 0; j < 1024; j++)
    {
        for(int k = 0; k < 10; k++)
        {
            ans += dp[flag][j][k];
            ans %= MOD;
        }
    }
    cout << ans << endl;
}