2014
11-30

# A Simple Problem

There’s one row of buttons lying on onmylove’s laptop keyboard, which are used to input the numbers,just as shown in the picture:

onmylove used to input the numbers with his two specifc fingers,, one is on the left, the other is on the right. In one unit time, onmylove’s two fingers can both operate. For each finger, each operation can be one of the following:
1.press on the button just under the finger.
2.move to the left button or the right button.

But there’re still some points you should pay attention to:
1. at any time, the left nger should at the left side of the right finger.
2. in one unit of time, only one of these two fingers can press the button under it. Of course, the other
finger can move at this unit of time.

Now you are given a string which consists of only numbers, you are asked to calculate: if onmylove want to input all these numbers, how many time does he need at least? At the every beginning, the left finger is above the button "5" and the right finger is above the button "6".

Multiple inputs. For each test case, there is one string at a line. It’s promised there’re only numbers in the string and the length of it is not more than 100.

Multiple inputs. For each test case, there is one string at a line. It’s promised there’re only numbers in the string and the length of it is not more than 100.

434
56
57
47

5
2
2
3

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <map>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <limits.h>
#include <queue>
#include <stack>

using namespace std;
int dp[110][11][11],b[110],len,ans;
char n[110];
void Init()
{
len=strlen(n);
for(int i=1;i<=len;i++)
{
b[i]=n[i-1]-'0';
if(b[i]==0)
b[i]=10;
}
memset(dp,-1,sizeof(dp));
dp[0][5][6]=0;
ans=9999999;
}
int ABS(int x,int y)
{
if(x-y>0)
return x-y;
else
return y-x;
}
void Solve()
{

for(int i=0;i<len;i++)
{
for(int l=1;l<=10;l++)
{
for(int r=l+1;r<=10;r++)
{
if(dp[i][l][r]>=0)
{
for(int R=b[i+1]+1;R<=10;R++)
{
if(dp[i+1][b[i+1]][R]<0 || dp[i+1][b[i+1]][R]>dp[i][l][r]+max(ABS(b[i+1],l)+1,ABS(R,r)))
{
dp[i+1][b[i+1]][R]=dp[i][l][r]+max(ABS(b[i+1],l)+1,ABS(R,r));
/* cout<<b[i+1]<<" "<<i<<" "<<l<<" "<<r<<" "<<R<<endl;
if(b[i+1]==5 && i==0 && l==5 && r==6 && R==7)
{
cout<<ABS(b[i+1],l)+1<<" "<<ABS(R,r)<<endl;
}*/
if(i==len-1)
{
ans=min(ans,dp[i+1][b[i+1]][R]);
}
}
}
for(int L=b[i+1]-1;L>=1;L--)
{
if(dp[i+1][L][b[i+1]]<0 || dp[i+1][L][b[i+1]]>dp[i][l][r]+max(ABS(L,l),ABS(b[i+1],r)+1))
{
dp[i+1][L][b[i+1]]=dp[i][l][r]+max(ABS(L,l),ABS(b[i+1],r)+1);
if(i==len-1)
{
ans=min(ans,dp[i+1][L][b[i+1]]);
}
}
}
}
}
}
}
// cout<<dp[1][5][7]<<endl;
}
int main()
{
while(scanf("%s",&n)!=EOF)
{
Init();
Solve();
printf("%d\n",ans);
}
return 0;
}

1. 为什么for循环找到的i一定是素数叻，而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak，而你每次取余都用的是原来的m，也就是n

2. 样例输出和程序输出不吻合，修改一下样例输出吧。我用的是VC编译器，会提示我的i和j变量重复定义

3. 换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
应该是，不可能小于合并后的第K小值吧