AtCode Code festival 2017qualC-D-dp+ 최적화

3094 단어 DP

전송문 제목: 문자열 s를 주고 s를 최소한 몇 조각으로 나누면 각 조각이 조합을 거친 후에 회문열이 될 수 있습니다.(|s|≤2e5)
Solution: 우리는'회문열'이라는 정의를 바꿀 수 있다. 모든 자모에 대해 우리는 이를 2진법의 0-25자리로 바꿀 수 있다. 그리고 만약에 문자열이 회문열이라면 이 문자열은 문자마다 0이나 2의 멱이 다르다. 그러면 이 문제는 dp로 풀 수 있다. f[i]는 앞의 i 문자의 나누어진 최소 단수를 나타낸다. 옮기는 것은 바로
f[i]=min(f[j]+1)(1≤j그런데 이렇게 n자로 쓰면 T가 떨어지는데 어떡하지?
기억화는 모든 하위 문자열 상태의 최소 단수를 저장할 수 있다. (하위 문자열 상태는 2진법으로 표시할 수 있다.) 그리고 이동할 때 2의 멱과 0을 매거하면 된다.
코드:

#include
#include
#include
using namespace std;
char s[200010];
int t[200010];
int f[200010];
int minn[(1<<26)+1];
int main()
{
    scanf("%s",s+1);
    for (int i=1;i<=strlen(s+1);i++)
        t[i]=t[i-1],t[i]^=(1<'a'));
    for (int i=0;i<=(1<<26)-1;i++) minn[i]=1e9;
    minn[0]=0;
    for (int i=1;i<=strlen(s+1);i++)
    {
        f[i]=1e9;
        for (int j=0;j<=25;j++)
            f[i]=min(f[i],minn[t[i]^(1<1);
        f[i]=min(f[i],minn[t[i]]+1);
        minn[t[i]]=min(minn[t[i]],f[i]);
    }
    printf("%d",f[strlen(s+1)]);
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다