装压DP......
http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=11450
J: You Win!
You just achieved the High Score on your favorite video game! Now, you get to enter
your name! You have to use the controller to enter your name, which can be awkward.
Here’s how it works:
There are only the 26 capital letters A to Z, in order. There are no numbers,
spaces, lower case letters, or any other characters.
Pushing UP or DOWN changes the active letter one letter forward (UP) or
backward (DOWN). The active letter starts at A. It will not reset when you move
around in the name. It also wraps: UP from Z goes to A, DOWN from A goes to Z.
Pushing LEFT or RIGHT moves the cursor one letter left or right in the current
name. Note that once the cursor is at either end of the current name, it cannot
move any further in that direction.
Pushing the FIRE button adds the active letter to the name.
For example, consider the name ‘ALMA’. One way you could enter ‘ALMA’ is like this:
Action # of Pushes Name (| = Cursor) Active Letter
FIRE 1 A| A
UP 11 A| L
FIRE 1 AL| L
UP 1 AL| M
FIRE 1 ALM| M
DOWN 12 ALM| A
FIRE 1 ALMA| A
This would take 28 button pushes. However, consider entering ‘ALMA’ like this:
Action # of Pushes Name (| = Cursor) Active Letter
FIRE 1 A| A
FIRE 1 AA| A
LEFT 1 A|A A
UP 11 A|A L
FIRE 1 AL|A L
UP 1 AL|A M
FIRE 1 ALM|A M
2013 ACM ICPC Southeast USA Regional Programming Contest
Page 16 of 16 2 November, 2013
This takes only 17 button pushes. Given a name, what is the fewest number of button
pushes needed to enter that name? Assume that the active letter starts at A, and that it
doesn’t matter where the cursor ends up when you’re done.
Input
There will be several test cases in the input. Each test case will consist of a single string
on its own line, with from 1 to 18 capital letters, representing a name that must be
entered into the High Score list. The input will end with a line with a single 0.
Output
For each test case, output a single integer representing the smallest number of button
pushes needed to enter the name. Output no spaces, and do not separate answers with
blank lines.
Sample Input
ALMA
YES
0
Sample
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int dp[1<<19][19],n;
char str[20];
int getD(char a,char c)
{
if(a>c) swap(a,c);
return min(c-a,a-‘A‘+‘Z‘-c+1);
}
int getSHIFT(int from,int to,int st)
{
int ans=0;
if(from<to)
{
for(int i=from;i<to;i++)
{
if(st&(1<<i)) ans++;
}
}
else
{
for(int i=from-1;i>to-1;i--)
{
if(st&(1<<i)) ans++;
}
}
return ans;
}
void solve()
{
memset(dp,63,sizeof(dp));
for(int i=0;i<19;i++) dp[0][i]=0;
for(int i=0;i<n;i++)
{
dp[1<<i][i+1]=getD(‘A‘,str[i])+1;
}
for(int i=1;i<(1<<n);i++)
{
for(int j=1;j<=n;j++)
{
///在状态i 光标在j
///PS1: 除状态0外光标必须在哪个字符后面,光标前面的字符即上一个字母,也就是从没有j-1号字母的
///状态转移过来的
if((i&(1<<(j-1)))==0) continue;
if(dp[i][j]!=INF) continue;
int k=j-1;
int ii=i^(1<<k);///从没有k号字符的状态开始转移 即状态ii-->状态i
for(int jj=1;jj<=n;jj++)///枚举状态ii的光标位置
{
if((ii&(1<<(jj-1)))==0) continue;
dp[i][j]=min(dp[i][j],dp[ii][jj]+getD(str[jj-1],str[j-1])+getSHIFT(jj,j,ii)+1);
}
}
}
int ans=INF;
for(int i=1;i<=n;i++) ans=min(ans,dp[(1<<n)-1][i]);
printf("%d\n",ans);
}
int main()
{
while(scanf("%s",str)!=EOF)
{
if(str[0]==‘0‘) break;
n=strlen(str);
solve();
}
return 0;
}