[정수리] codeforces 137D Palindromes (dp 신제 루트 인쇄)

제목:
하나의 열을 k개의 회문열로 나누는 데 필요한 최소한의 조작수를 구하십시오. 이 조작은 열의 어느 위치의 값을 바꾸어 나누어진 열이 회문이 될 수 있도록 하는 것입니다.
문제 풀이:
신제야, 경로 인쇄가 매우 어려워.
첫째, 우리는 하구간 [i, j]의 상열이 회문으로 변하는 조작수를 미리 처리해야 한다!이 단계는 구간 dp를 사용하여 미리 처리하고 구간과 새것을 끊임없이 구분해야 한다.
둘째, dp는 가장 작은 조작수를 계산한다. dp[i][j]는 전 j개의 점을 i부 회문열로 나누는 데 필요한 최소 조작수를 나타낸다.
셋째, 얻으려면 두 번째 단계에서 dp의 값을 가지고 경로를 거꾸로 추측해야 한다. 이 판단을 통해
if(dp[i][later]=dp[i-1][j]+cost[j+1][later])는 끊임없이 새로운 later와 거꾸로 밀어붙여 후효성을 방지한다!
경로의 표시는mark[i]로 첫 번째 접점의 위치를 표시합니다.
이거 아직 안 끝났어요. 분할하면 같은 상황이 생길 수 있으니까 무게를 재야 돼요!!if(mark[i-1]!=mark[i]) mark[cnt++]=mark[i]
이것들을 다 한 후에 문자열을 수정하기 시작할 수 있습니다. 단어는 수정된 문자열을 출력해야 합니다. 이 단계는 비교적 기교가 있습니다. 구체적인 것은 코드를 보십시오!
넷째, 인쇄 경로는 간단하다.mark[i]가 표시한 위치를 직접 통과한 다음에 대응하는 위치에서'+'를 출력한다.
진심은 신제!어려운 점은 주로 세 번째 경로의 획득 처리에 있다. 그야말로 이해할 수 없다!

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<map>
using namespace std;
typedef long long lld;
const int oo=0x3f3f3f3f;
const lld OO=1LL<<61;
const int MOD=1000000007;
#define maxn 505
int dp[maxn][maxn];
int cost[maxn][maxn];
int mark[maxn];
char str[maxn];
int n,k;

void TheCnt()
{
    n=strlen(str+1);
    memset(cost,0,sizeof cost);
    for(int j=1;j<=n;j++)
        for(int i=1;i<=j;i++)
            cost[i][j]=cost[i+1][j-1]+(str[i]!=str[j]);
}

void Dp()
{
    memset(dp,0x3f,sizeof dp);
    dp[0][0]=0;
    for(int i=1;i<=k;i++)
    {
        for(int j=i;j<=n;j++)
        {
            for(int jj=i-1;jj<=j;jj++)
            if(dp[i-1][jj]!=oo)
            {
                dp[i][j]=min(dp[i-1][jj]+cost[jj+1][j],dp[i][j]);
            }
        }
    }
    printf("%d
",dp[k][n]);
}

void output()
{
    int cnt;
    int later=n;
    for(int i=k;i>=1;i--)
    {
        for(int j=1;j<=n;j++)
        {
            if(dp[i-1][j]!=oo&&dp[i][later]==dp[i-1][j]+cost[j+1][later])
            {
                mark[i]=j+1;
                later=j;
                break;
            }

        }
    }
    mark[k+1]=n+1;
    mark[1]=1;
    cnt=1;
///        
///  ：
    for(int i=1;i<=k+1;i++)
        if(mark[i-1]!=mark[i])
            mark[cnt++]=mark[i];
    cnt-=2;//   cnt+1 
    mark[cnt+1]=n+1;
///     ：
    for(int i=1;i<=cnt;i++)
    {
        int u=mark[i],v=mark[i+1]-1;
        while(u<v)
        {
            if(str[u]!=str[v])
                str[v]=str[u];
            u++;
            v--;
        }
    }
    cnt=2;//         +       ！！
    for(int i=1;i<=n;i++)
    {
        printf("%c",str[i]);
        if(i==mark[cnt]-1)
        {
            if(mark[cnt]!=n+1)printf("+");
            cnt++;
        }
    }
    puts("");
}

int main()
{
    while(scanf("%s%d",str+1,&k)!=EOF)
    {
        TheCnt();
        Dp();
        output();
    }
    return 0;
}
/**
abacaba
1
abdcaba
2
abdcaba
5
abacababababbcbabcd
3


*/