2019CCPC秦皇岛 I HDU6739 Invoker【简单dp/暴力】

题意：

有十种连续三个的字母组合代表不同的操作，给你一个操作序列，问最少需要多少字母；

分析：

只要求最终结果而不要求答案序列，考虑dp；

对于操作序列而言，当前操作需要的字母数只与上一个操作的字母排列有关，三个字母至多有6种排列，那么就从上一个操作的排列转移到当前操作，向后更新；

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
string p[]={"QQQ","QQW","QQE","WWW","QWW","WWE","EEE","QEE","WEE","QWE"};
char q[]={'Y','V','G','C','X','Z','T','F','D','B'};
const int maxn=1e5+7;
char s[maxn];
struct node
{
string a[8];
}arr[15];
map<char,int> mp;
int dp[maxn][10];
void init()
{
for (int i=0;i<10;i++) arr[i+1].a[0]=p[i];
for (int i=0;i<10;i++) mp[q[i]]=i+1;
for (int i=1;i<=10;i++)//处理出每个组合的所有排列
{
char tmp[5];
for (int j=0;j<3;j++) tmp[j]=arr[i].a[0][j];
sort(tmp,tmp+3);
int kk=0;
do
{
arr[i].a[kk]="";
for (int j=0;j<3;j++) arr[i].a[kk]+=tmp[j];
kk++;
}
while(next_permutation(tmp,tmp+3));
}
}
int main()
{
init();
while(~scanf("%s",s))
{
int st=strlen(s);
for (int i=0;i<6;i++) dp[0][i]=3;
int ff,f;
for (int i=1;i<st;i++)
{
f=mp[s[i]];
for (int j=0;j<6;j++)
{
if(arr[f].a[j]=="") continue;
dp[i][j]=INF;
for (int jj=0;jj<6;jj++)
{
ff=mp[s[i-1]];
if(arr[ff].a[jj]=="") continue;
dp[i][j]=min(dp[i-1][jj]+3,dp[i][j]);
for (int k=0;k<3;k++)
{
int flag=1,res=0;
for (int kk=k;kk<3;kk++)
if(arr[f].a[j][res++]!=arr[ff].a[jj][kk]) {flag=0;break;}
if(flag) dp[i][j]=min(dp[i-1][jj]+k,dp[i][j]);
}
}
}
}
int ans=INF;
for (int i=0;i<6;i++) if(dp[st-1][i]) ans=min(ans,dp[st-1][i]);
printf("%dn",ans+st);
}
}

最后

以上就是曾经台灯为你收集整理的2019CCPC秦皇岛 I HDU6739 Invoker【简单dp/暴力】的全部内容，希望文章能够帮你解决2019CCPC秦皇岛 I HDU6739 Invoker【简单dp/暴力】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。