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

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

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

dp[t,i,j]表示已經(jīng)擊打了t個(gè)字符的最少步數(shù)
這樣子的話,轉(zhuǎn)移時(shí)只計(jì)算將手指移動(dòng)到目標(biāo)位置處的代價(jià),這樣子會(huì)很快!!
假設(shè)目標(biāo)位置為p,這樣更新
dp[pre,i,j] --> dp[now,ii,p]
dp[now,p,jj]
這樣子計(jì)算的狀態(tài)很少,而且這種貪心的做法是正確的,只計(jì)算到目標(biāo)位置!!

啟示:劃分階段要注意,劃分出來的階段越少更好點(diǎn),而且注意計(jì)算狀態(tài)時(shí)可以貪心,只計(jì)算有用的??!

*/
#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;
}
|