2018CCCC-L3-2: 최대 3자(DP)

L3-2 - 3자 이상 삭제 (30분)
소문자 영문 자모로 구성된 모든 문자열을 정해 주십시오. 세 글자를 더 삭제할 수 있도록 해 주십시오. 그 결과 몇 가지 다른 문자열이 있을 수 있습니까?

입력 형식:

한 줄에 소문자로 구성된 길이가 구간 [4, 10^6]에 있는 문자열을 입력하십시오.

출력 형식:

한 줄에서 세 글자를 삭제한 후 다른 문자열의 개수를 출력합니다.

샘플 입력:

ababcc

출력 예제:

25

팁:
0자를 삭제하면 "ababcc"를 얻을 수 있습니다.
1글자를 삭제하면 "babcc", "aabcc", "abbcc", "abacc", "ababc"를 얻을 수 있습니다.
두 문자를 삭제하면 "abcc", "bbcc", "bacc", "babc", "aacc", "aabbc", "abbc", "abac", "ababab"를 얻을 수 있습니다.
세 글자를 삭제하면 "abc", "bcc", "acc", "bbc", "bac", "bab", "aac", "aabb", "abb", "abb"를 얻을 수 있습니다.
 
사고방식: d[i][j]는 전 i자에서 j자를 삭제한 후 얻은 서로 다른 문자열의 개수를 나타낸다.... 해야 한다
d[i][j+1]+=d[i-1][j](i자 삭제)
d[i][j]+=d[i-1][j](i자 삭제 안함)
이렇게 옮기기만 하면 중복될 거야.예를 들어 하나의 문자열 cdabnaxy를 사용하면 abn을 삭제하고bna를 삭제한 문자열은 모두 cdaxy입니다.
이때 무게를 줄여야 한다. 위의 밤을 보면 한 문자에 대한 s[i]를 발견할 수 있다. 만약에 i 이전에 x가 s[x]=s[i]가 존재했다면 [x, i-1] 사이의 문자를 삭제하고 [x+1, i] 사이의 문자를 삭제하는 것이 사실 중복되고 등가였다면 d[i][j]는 d[x-1][j-(i-x)]를 줄이고 이 부분의 중복열을 삭제해야 한다.

#include
using namespace std;
const int MAX=1e6+5;
typedef long long ll;
char s[MAX];
ll d[MAX][4];
int main()
{
    scanf("%s",s+1);
    int n=strlen(s+1);
    d[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=3;j++)
        {
            if(d[i-1][j]==0)continue;
            if(j<3)d[i][j+1]+=d[i-1][j];
            d[i][j]+=d[i-1][j];
            for(int k=i-1;k>=1&&i-k<=j;k--)//       k  s[k]=s[i]
            {
                if(s[k]==s[i])
                {
                    d[i][j]-=d[k-1][j-(i-k)];
                    break;
                }
            }
        }
    }
    printf("%lld
",d[n][0]+d[n][1]+d[n][2]+d[n][3]);
    return 0;
}