这个题目上周的对抗赛的，美国2013区域赛的题目，上次比赛真惨，就做出一道题，最多的也只做出两道，当时想把这题做出来，一直TLE。
这个题目用挂在Hunnu OJ的数据可以过，但UVALive上死活过不了，好像UVALive卡的时间不太对，没人过了这道题。
我当初是想用一个dp[s]表示键入状态，然后由dp[0]开始逐渐向上深搜，结果就TLE了，后来比较了一下别人的代码，，果然我这样还是不行
不管我怎么优化，我这一维数组，不能对某个状态马上就返回，因为随时可以再被更新，但是如果用个二维数组，dp[s][i],表示在状态为s的时候，键入第i个字符时候的最小键入数目，就可以只更新一次，下次再遇到这个情况就能马上return了
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define N 18 #define INF 1<<30 using namespace std; char ch[N]; int len,dp[1<<N][N],ALL; //int up[1<<N][N]; /* int abs(int a,int b) { if (a>b) return a-b; else return b-a; } */ int diff(int a, int b) //这个函数和下面的函数都是计算转换字符的按键数，结果下面那个是错的，原因是在计算从Z字母转换过去的时候，下面那个算错了，没照顾到a在b的后面的情况。为了这个BUG我检查了好久 真不应该啊 { int ans=abs(a-b); return min(ans,‘Z‘-‘A‘-ans+1); } int ccounts(char a,char b) { int asc1=a-‘A‘; int asc2=b-‘A‘; int z=‘Z‘-‘A‘; int press=abs(asc1-asc2); press=min((press),z-asc2+1+asc1); return press; } /* void solve(int s,int d) { if (d==len) return; //if (vis[s]) return; vis[s]=1; if (dp[ALL]<=dp[s]) return; for (int i=0; i<len; i++) { if ((1<<i)&s) continue; int nt=s+(1<<i); int tmp; //cout<<"p1"<<endl; //if (up[s][i]==0) //up[s][i]=counts(i,s,ch[i]); tmp=dp[s]+counts(i,s,ch[i]); //cout<<"p2"<<endl; //cout<<tmp<<endl; if (dp[nt]>tmp) { dp[nt]=tmp; mouse[nt]=i+1; action[nt]=ch[i]-‘A‘; solve(nt,d+1); } else if (vis[nt]==0) solve(nt,d+1); //cout<<"p3"<<endl; //cout<<dp[nt]<<endl; } } */ int solve (int s,int last) //记忆化搜索 { if (dp[s][last]) return dp[s][last]; if (s==0) return 0; dp[s][last]=INF; int pos=0; for (int i=0;i<=last;i++) { if ((1<<i)&s) pos++; } for (int i=0,j=0;i<len;i++) { if ((1<<i)&s) { j++; if (j==pos) continue; int cur= j>pos? j-pos:pos-j-1; int rng=diff(ch[i],ch[last]); dp[s][last]=min(dp[s][last],1+cur+rng+solve(s^(1<<last),i)); } } return dp[s][last]; } int main() { //init(); while (scanf("%s",ch)) { len=strlen(ch); if (len==1 && ch[0]==‘0‘) break; memset(dp,0,sizeof dp); ALL=1<<len; ALL--; for (int i=0;i<len;i++) { dp[1<<i][i]=diff(‘A‘,ch[i])+1; } int ans=INF; for (int i=0;i<len;i++){ ans=min(ans,solve(ALL,i)); } printf("%d\n",ans); } return 0; }