 /**//*
題意: 一列按鈕1,2 .9,0 現要按出一個序列,兩個手指,開始時左手在5,右手在6
問最少按的次數 序列只有100

轉移比較明顯,從(i,j)轉移到 (i+1,j+1),(i+1,j),(i+1,j-1) (i-1,j-1)
可以用bfs做

但如果面對規模10^6時,就會很慢
如果表示成dp[t,i,j],已經進行了t步,目前在(i,j)位置最多已擊打的序列個數
當dp[t,i,j] = len時t即為答案,但這樣子也會太慢

dp[t,i,j]表示已經擊打了t個字符的最少步數
這樣子的話,轉移時只計算將手指移動到目標位置處的代價,這樣子會很快??!
假設目標位置為p,這樣更新
dp[pre,i,j] --> dp[now,ii,p]
dp[now,p,jj]
這樣子計算的狀態很少,而且這種貪心的做法是正確的,只計算到目標位置!!

啟示:劃分階段要注意,劃分出來的階段越少更好點,而且注意計算狀態時可以貪心,只計算有用的?。?br>
*/
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int MAXN = 100010;
const int INF = 1000000000;

 inline int min(int a,int b) {return a<b?a:b;}

int dp[2][11][11];
int pre,now;
char str[MAXN];

void updateL(int l,int r,int p)//l->p
  {
if(p==10)return;
int dist = abs(p-l)+1,tmp = dp[pre][l][r]+dist;
for(int t=0;t<=dist && r+t<=10;t++)
dp[now][p][r+t] = min(dp[now][p][r+t],tmp);
for(int t=0;t<=dist && r-t>=1;t++)
dp[now][p][r-t] = min(dp[now][p][r-t],tmp);
}

void updateR(int l,int r,int p)//r->p
  {
if(p==1)return;
int dist = abs(p-r)+1,tmp = dp[pre][l][r]+dist;
for(int t=0;t<=dist && l+t<=10;t++)
dp[now][l+t][p] = min(dp[now][l+t][p],tmp);
for(int t=0;t<=dist && l-t>=1;t++)
dp[now][l-t][p] = min(dp[now][l-t][p],tmp);
}

int main()
  {
while(~scanf("%s",str))
 {
pre = 0,now = 1;
for(int i=1;i<10;i++)
for(int j=i+1;j<=10;j++)
dp[pre][i][j] = INF;
dp[pre][5][6] = 0;
int t;
for(int n=0;str[n];n++)
 {
t = str[n]-'0';
if(t==0)t = 10;
for(int i=1;i<=10;i++)
for(int j=1;j<=10;j++)
dp[now][i][j] = INF;
for(int i=1;i<10;i++)
for(int j=i+1;j<=10;j++)
if(dp[pre][i][j] != INF)
 {
updateL(i,j,t);
updateR(i,j,t);
}
swap(now,pre);
}
int ans = INF;
for(int i=1;i<=10;i++)
 {
ans = min(ans,dp[pre][t][i]);
ans = min(ans,dp[pre][i][t]);
}
printf("%d\n",ans);
}
return 0;
}
|