题意：http://acm.hdu.edu.cn/showproblem.php?pid=6739
尽量让他们连起来。
思路：
直接dp，其中一个状态是以什么结尾。
1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0); 2 #include <cstdio>//sprintf islower isupper 3 #include <cstdlib>//malloc exit strcat itoa system("cls") 4 #include <iostream>//pair 5 #include <fstream>//freopen("C:\Users\13606\Desktop\草稿.txt","r",stdin); 6 #include <bitset> 7 //#include <map> 8 //#include<unordered_map> 9 #include <vector> 10 #include <stack> 11 #include <set> 12 #include <string.h>//strstr substr 13 #include <string> 14 #include <time.h>//srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9; 15 #include <cmath> 16 #include <deque> 17 #include <queue>//priority_queue<int, vector<int>, greater<int> > q;//less 18 #include <vector>//emplace_back 19 //#include <math.h> 20 //#include <windows.h>//reverse(a,a+len);// ~ ! ~ ! floor 21 #include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare) 22 using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation 23 //****************** 24 int abss(int a); 25 int lowbit(int n); 26 int Del_bit_1(int n); 27 int maxx(int a,int b); 28 int minn(int a,int b); 29 double fabss(double a); 30 void swapp(int &a,int &b); 31 clock_t __STRAT,__END; 32 double __TOTALTIME; 33 void _MS(){__STRAT=clock();} 34 void _ME(){__END=clock();__TOTALTIME=(double)(__END-__STRAT)/CLOCKS_PER_SEC;cout<<"Time: "<<__TOTALTIME<<" s"<<endl;} 35 //*********************** 36 #define rint register int 37 #define fo(a,b,c) for(rint a=b;a<=c;++a) 38 #define fr(a,b,c) for(rint a=b;a>=c;--a) 39 #define mem(a,b) memset(a,b,sizeof(a)) 40 #define pr printf 41 #define sc scanf 42 #define ls rt<<1 43 #define rs rt<<1|1 44 typedef long long ll; 45 const double E=2.718281828; 46 const double PI=acos(-1.0); 47 //const ll INF=(1LL<<60); 48 const int inf=(1<<30); 49 const double ESP=1e-9; 50 const int mod=(int)1e9+7; 51 const int N=(int)1e5+10; 52 53 int dp[N][50]; 54 char s[N]; 55 int tot; 56 int ID[400]; 57 int map[50]; 58 int id(int x) 59 { 60 return ID[x]; 61 } 62 struct node 63 { 64 int a,b,c; 65 }p[10]; 66 void PR(int _[],int n) 67 { 68 for(int i=1;i<=n;++i) 69 pr("%d ",_[i]); 70 pr(" "); 71 } 72 int main() 73 { 74 tot=0; 75 for(int i=1;i<=350;++i) 76 { 77 int temp=i; 78 bool f=1; 79 while(temp>0) 80 { 81 if(temp%10!=1&&temp%10!=2&&temp%10!=3) 82 f=0; 83 temp/=10; 84 } 85 if(f)map[++tot]=i; 86 } 87 for(int i=1;i<=45;++i) 88 ID[map[i]]=i; 89 p[1]={1,2,3}; 90 p[2]={1,3,2}; 91 p[3]={2,1,3}; 92 p[4]={2,3,1}; 93 p[5]={3,1,2}; 94 p[6]={3,2,1}; 95 int v[200]; 96 v['Y']=111; 97 v['V']=112; 98 v['G']=113; 99 v['C']=222; 100 v['X']=122; 101 v['Z']=223; 102 v['T']=333; 103 v['F']=133; 104 v['D']=233; 105 v['B']=123; 106 while(~sc("%s",s+1)) 107 { 108 int l=strlen(s+1); 109 for(int i=1;i<=l;++i) 110 for(int j=1;j<=45;++j) 111 dp[i][j]=inf; 112 for(int i=1;i<=6;++i) 113 { 114 int temp=v[s[1]]; 115 int cnt=3; 116 int mp[5]; 117 while(temp>0) 118 { 119 mp[cnt]=temp%10; 120 temp/=10; 121 cnt--; 122 } 123 int x=mp[p[i].b]*10+mp[p[i].c]; 124 dp[1][id(mp[p[i].a]*100+mp[p[i].b]*10+mp[p[i].c])]=min(3,dp[1][id(mp[p[i].a]*100+mp[p[i].b]*10+mp[p[i].c])]); 125 dp[1][id(x)]=min(dp[1][id(x)],3); 126 x=mp[p[i].c]; 127 dp[1][id(x)]=min(dp[1][id(x)],3); 128 } 129 //PR(dp[1],37); 130 int ans=0; 131 for(int i=2;i<=l+1;++i) 132 { 133 int min_=inf; 134 for(int j=1;j<=45;++j) 135 min_=min(min_,dp[i-1][j]); 136 ans=min_; 137 if(i==l+1)break; 138 139 int temp=v[s[i]]; 140 int cnt=3; 141 int mp[5]; 142 while(temp>0) 143 { 144 mp[cnt]=temp%10; 145 temp/=10; 146 cnt--; 147 } 148 for(int j=1;j<=6;++j) 149 { 150 int x=mp[p[j].a],y=mp[p[j].b],z=mp[p[j].c]; 151 // cout<<x<<' '<<y<<' '<<z<<endl; 152 dp[i][id(x*100+y*10+z)]=min(dp[i][id(x*100+y*10+z)],min(min(dp[i-1][id(x)]+2,min(min_+3,dp[i-1][id(x*10+y)]+1)),dp[i-1][id(x*100+y*10+z)])); 153 dp[i][id(y*10+z)]=min(dp[i][id(y*10+z)],min(min(dp[i-1][id(x)]+2,min(min_+3,dp[i-1][id(x*10+y)]+1)),dp[i-1][id(x*100+y*10+z)])); 154 dp[i][id(z)]=min(dp[i][id(z)],min(min(dp[i-1][id(x)]+2,min(min_+3,dp[i-1][id(x*10+y)]+1)),dp[i-1][id(x*100+y*10+z)])); 155 } 156 // PR(dp[i],37); 157 } 158 pr("%d ",ans+l); 159 } 160 return 0; 161 } 162 163 /**************************************************************************************/ 164 165 int maxx(int a,int b) 166 { 167 return a>b?a:b; 168 } 169 170 void swapp(int &a,int &b) 171 { 172 a^=b^=a^=b; 173 } 174 175 int lowbit(int n) 176 { 177 return n&(-n); 178 } 179 180 int Del_bit_1(int n) 181 { 182 return n&(n-1); 183 } 184 185 int abss(int a) 186 { 187 return a>0?a:-a; 188 } 189 190 double fabss(double a) 191 { 192 return a>0?a:-a; 193 } 194 195 int minn(int a,int b) 196 { 197 return a<b?a:b; 198 }