Codeforces Round #349 (Div. 2) C. Reberland Linguistics DP

4669 단어
제목: 반나절 동안 문제를 읽었는데 과감하게 제목의 뜻을 이해하지 못했어. 풀이를 보고서야 이 뜻을 알았지.
문자열을 주고 길이가 적어도 5인 접두사를 제거하고 나머지는 길이가 2 또는 3인 꼬치로 자르고 인접한 꼬치가 같지 않으니 마지막에 몇 개의 꼬치로 잘라도 되는지 물어보세요.
아이디어:
dp[i][2]=1은 i, i+1으로 이루어진 직렬이 요구를 충족시킬 수 있음을 나타낸다. dp[i][3]==1은 같은 이치이다.그리고 옮겼다.
i 위치를 고려하면 길이는 2입니다.
(1) (i, i+1)이 (i+2, i+3)와 같으면 dp[i+2][3]===1일 때 dp[i][2]=1;
(i, i+1)이 (i+2, i+3)와 다르면 dp[i+2][2]=1 또는 dp[i+2][3]===1일 때 dp[i][2]=1;
(2) (i, i+1, i+2)와 (i+3, i+4, i+5)가 같으면 dp[i+3][2]===1일 때 dp[i][3]=1;
만약 다르면 dp[i+3][2]=1 또는 dp[i+3][3]==1일 때 dp[i][3]=1;

코드

#include
#include
#include
#include
#include
using namespace std;
const int N=1e5+5;
bool d[N][4];
int main()
{
    string s;
    cin>>s;
    if(s.size()<=6){
        printf("0
");return 0;
    }
    int n=s.size();
    d[n][2]=d[n][3]=1;
    vector<string>ans;
    for(int i=n-2;i>=5;i--){
        string now(s,i,2);
        string next(s,i+2,2);
        d[i][2]=(now!=next)&&d[i+2][2];
        d[i][2]=d[i][2]||d[i+2][3];
        if(d[i][2])ans.push_back(now);
        if(i==n-2)continue;
        string now1(s,i,3);
        string next1(s,i+3,3);
        d[i][3]=(now1!=next1)&&d[i+3][3];
        d[i][3]=d[i][3]||d[i+3][2];
        if(d[i][3])ans.push_back(now1);
    }
    sort(ans.begin(),ans.end());
    int sum=0;
    ans.push_back("");
    for(int i=0;i1;i++)
        if(ans[i]!=ans[i+1])sum++;
    cout<"
";
    for(int i=0;i1;i++)
        if(ans[i]!=ans[i+1])cout<"
";
    return 0;
}

전재 대상:https://www.cnblogs.com/01world/p/5651220.html
Storyboard에서 UIView의 테두리, 모서리, 그림자를 설정하는 Extension
[HTML] 시맨틱(semantic) 태그

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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