HDU

题意

给你长度为3的字符串其可以变成{B, C, D, F, G, T, V, X, Y, Z}中的一种。

给你一字符串str有{B, C, D, F, G, T, V, X, Y, Z}组成，让你变成相应的长度为3的字符串且要加R使其变成{B, C, D, F, G, T, V, X, Y, Z}中一种比如QQQR就变成了Y。

长度为三的字符串顺序不定

思路

将无序的长度为3的字符串全排列写出来，然后根据条件写状态转移方程

每种长度为3的字符串最多的排列是6种，后一种由前一种变化而来

状态转移方程：

(dp[i][j]=min(dp[i][j],dp[i-1][k]+cal(mt[str[i-1]],mt[str[i]],k,j));)

(cal)表示第(i)个字符下由(str[i-1])的第(k)种排列变到(str[i])的第(j)种排列的最小代价，然后更新就可以。

#include<bits/stdc++.h>
using namespace std;


const int maxn=1e5+10;

int dp[maxn][6];
char str[maxn];
char s[10][6][4]= {
    {"QQQ","QQQ","QQQ","QQQ","QQQ","QQQ"},
    {"QQW","QWQ","WQQ","WQQ","WQQ","WQQ"},
    {"EQQ","QEQ","QQE","QQE","QQE","QQE"},
    {"WWW","WWW","WWW","WWW","WWW","WWW"},
    {"QWW","WQW","WWQ","WWQ","WWQ","WWQ"},
    {"EWW","WEW","WWE","WWE","WWE","WWE"},
    {"EEE","EEE","EEE","EEE","EEE","EEE"},
    {"EEQ","EQE","QEE","QEE","QEE","QEE"},
    {"EEW","WEE","EWE","EWE","EWE","EWE"},
    {"EQW","EWQ","QEW","WEQ","QWE","WQE"}
};

map<char,int>mt;
int cal(int x,int y,int j,int k) {
    if(s[x][j][0]==s[y][k][0]&&s[x][j][1]==s[y][k][1]&&s[x][j][2]==s[y][k][2]) return 0;
    else if(s[x][j][1]==s[y][k][0]&&s[x][j][2]==s[y][k][1]) return 1;
    else if(s[x][j][2]==s[y][k][0]) return 2;
    return 3;

}

int main() {
    while(~scanf("%s",str)) {
        int len=strlen(str);
        mt['Y']=0,mt['V']=1,mt['G']=2,mt['C']=3,mt['X']=4;
        mt['Z']=5,mt['T']=6,mt['F']=7,mt['D']=8,mt['B']=9;
        int ans=len;
        for(int i=0; i<maxn; ++i) {
            for(int j=0; j<6; ++j) {
                dp[i][j]=2e9;
            }
        }
        for(int i=0;i<6;++i){
            dp[0][i]=3;
        }
        for(int i=1; i<len; ++i) {
            for(int j=0; j<6; ++j) {
                for(int k=0; k<6; ++k) {
                    dp[i][j]=min(dp[i][j],dp[i-1][k]+cal(mt[str[i-1]],mt[str[i]],k,j));
                }
            }
        }
        int minn=dp[len-1][0];
        for(int i=0; i<6; ++i) {
            minn=min(minn,dp[len-1][i]);
        }
        printf("%d
",ans+minn);
    }




}