![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*
题意: 一列按钮1,2 .9,0 现要按出一个序列,两个手指,开始时左手在5,右手在6
问最少按的次数 序列只有100
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
转移比较明显,从(i,j)转移到 (i+1,j+1),(i+1,j),(i+1,j-1) (i-1,j-1)
可以用bfs做
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
但如果面对规模10^6时,就会很慢
如果表示成dp[t,i,j],已经进行了t步,目前在(i,j)位置最多已击打的序列个数
当dp[t,i,j] = len时t即为答案,但这样子也会太慢
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
dp[t,i,j]表示已经击打了t个字符的最少步数
这样子的话,转移时只计算将手指移动到目标位置处的代价,这样子会很快!!
假设目标位置为p,这样更新
dp[pre,i,j] --> dp[now,ii,p]
dp[now,p,jj]
这样子计算的状态很少,而且这种贪心的做法是正确的,只计算到目标位置!!
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
启示:划分阶段要注意,划分出来的阶段越少更好点,而且注意计算状态时可以贪心,只计算有用的!!
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MAXN = 100010;
const int INF = 1000000000;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) inline int min(int a,int b) {return a<b?a:b;}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int dp[2][11][11];
int pre,now;
char str[MAXN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void updateL(int l,int r,int p)//l->p
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
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);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void updateR(int l,int r,int p)//r->p
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
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);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
while(~scanf("%s",str))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
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++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
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)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
updateL(i,j,t);
updateR(i,j,t);
}
swap(now,pre);
}
int ans = INF;
for(int i=1;i<=10;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
ans = min(ans,dp[pre][t][i]);
ans = min(ans,dp[pre][i][t]);
}
printf("%d\n",ans);
}
return 0;
}
|