2018CCCC-L3-2: 최대 3자(DP)
소문자 영문 자모로 구성된 모든 문자열을 정해 주십시오. 세 글자를 더 삭제할 수 있도록 해 주십시오. 그 결과 몇 가지 다른 문자열이 있을 수 있습니까?
입력 형식:
한 줄에 소문자로 구성된 길이가 구간 [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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
