/**//* 题意: 一列按钮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] 这样子计算的状态很少,而且这种贪心的做法是正确的,只计算到目标位置!!
启示:划分阶段要注意,划分出来的阶段越少更好点,而且注意计算状态时可以贪心,只计算有用的!!
*/ #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; }
|