CCPC2019秦皇岛 I. Invoker-dp

题目：

思路：每个技能就6个状态，直接dp转移就可以了。

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

char c[100005], s[3];
map<char, char *> mp;

struct node{
    char s[3];
    char c[6][3];

}a[500005];

int tot=0;
int vis[3]={0};
int dp[100005][6]={0};
void dfs(int T, char s[], int i, int n){

    if(i==n){

        for(int j=0; j<3; j++){
            a[T].c[tot][j]=s[j];
        }
        tot++;
        return ;
    }

    for(int j=0; j<3; j++){
        if(!vis[j]){
            s[i]=a[T].s[j];
            vis[j]=1;
            dfs(T, s, i+1, n);
            vis[j]=0;
        }
    }
}

int sum(int i, int j, int k){

    if(a[i].c[j][0]==a[i-1].c[k][0]&&a[i].c[j][1]==a[i-1].c[k][1]&&a[i].c[j][2]==a[i-1].c[k][2]){
        return 3;
    }
    if(a[i].c[j][1]==a[i-1].c[k][0]&&a[i].c[j][2]==a[i-1].c[k][1]){
        return 2;
    }
    if(a[i].c[j][2]==a[i-1].c[k][0]){
        return 1;
    }
    return 0;
}

int main()
{
    mp['Y']="QQQ"; mp['V']="QQW"; mp['G']="QQE";
    mp['C']="WWW"; mp['X']="QWW"; mp['Z']="WWE";
    mp['T']="EEE"; mp['F']="QEE"; mp['D']="WEE";
    mp['B']="QWE";
    
    scanf("%s", c+1);
    int n=strlen(c+1);
    for(int i=1; i<=n; i++){
        a[i].s[0]=mp[c[i]][0];
        a[i].s[1]=mp[c[i]][1];
        a[i].s[2]=mp[c[i]][2];
        sort(a[i].s, a[i].s+3);
        tot=0;
        dfs(i, s, 0, 3);
    }

    memset(dp, 1, sizeof(dp));
    dp[1][0]=dp[1][1]=dp[1][2]=dp[1][3]=dp[1][4]=dp[1][5]=4;

    for(int i=2; i<=n; 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]+4-sum(i, j, k));
            }
        }
    }

    int MIN=10000000;
    for(int i=0; i<6; i++){
        MIN=min(MIN, dp[n][i]);
    }
    printf("%d\n", MIN);

    return 0;
}

HDU 6739

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

char c[1000005], s[3];
map<char, char *> mp;

struct node{
    char s[3];
    char c[6][3];

}a[1000005];

int tot=0;
int vis[3]={0};
int dp[1000005][6]={0};
void dfs(int T, char s[], int i, int n){

    if(i==n){

        for(int j=0; j<3; j++){
            a[T].c[tot][j]=s[j];
        }
        tot++;
        return ;
    }

    for(int j=0; j<3; j++){
        if(!vis[j]){
            s[i]=a[T].s[j];
            vis[j]=1;
            dfs(T, s, i+1, n);
            vis[j]=0;
        }
    }
}

int sum(int i, int j, int k){

    if(a[i].c[j][0]==a[i-1].c[k][0]&&a[i].c[j][1]==a[i-1].c[k][1]&&a[i].c[j][2]==a[i-1].c[k][2]){
        return 3;
    }
    if(a[i].c[j][1]==a[i-1].c[k][0]&&a[i].c[j][2]==a[i-1].c[k][1]){
        return 2;
    }
    if(a[i].c[j][2]==a[i-1].c[k][0]){
        return 1;
    }
    return 0;
}

int main()
{
    mp['Y']="QQQ"; mp['V']="QQW"; mp['G']="QQE";
    mp['C']="WWW"; mp['X']="QWW"; mp['Z']="WWE";
    mp['T']="EEE"; mp['F']="QEE"; mp['D']="WEE";
    mp['B']="QWE";

    while(~scanf("%s", c+1)){

        int n=strlen(c+1);
        for(int i=1; i<=n; i++){
            a[i].s[0]=mp[c[i]][0];
            a[i].s[1]=mp[c[i]][1];
            a[i].s[2]=mp[c[i]][2];
            tot=0;
            dfs(i, s, 0, 3);
        }

        memset(dp, 1, sizeof(dp));
        dp[1][0]=dp[1][1]=dp[1][2]=dp[1][3]=dp[1][4]=dp[1][5]=4;

        for(int i=2; i<=n; 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]+4-sum(i, j, k));
                }
            }
        }

        int MIN=10000000;
        for(int i=0; i<6; i++){
            MIN=min(MIN, dp[n][i]);
        }
        printf("%d\n", MIN);
    }
    return 0;
}