dp hdu-4433 locker

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4433

题目大意：

给两个长度相等的数字串s1,s2。每次操作可以把连续的最多三位都+1或-1，如果超过9则变成0，如果小于0则变成9.问从s1到s2最少的步数。

解题思路：

每一位移动正确最多5位，如果一位一位的移动最多需要1000*5=5000 。

长度有1000太大，不能直接用BFS。

因为每次改变最多只影响3位，前面的i-3位不改变，所以可以设dp[i][j][k]表示处理到了第i位，且最后两位分别为j,k时，前面的i-2位为原串s1时，达到最终的s2的前i位时移动的最小的步数。

转移时，先把第i位移动正确，然后枚举在移动第i位时，前面两位可能到达的状态，此时第i-2位移动的步数要小于等于第i-1位的，第i-1位的要小于等于第i位的，然后根据dp[i-1]的状态更新dp[i]的状态。

比如有三位分别需要移动2 3 4位第3位需要移动4位，在移动第3位时，可以先都移动2位，然后再后两位移动1位，最后一位再移动一位。

这类的dp做的比较少，以后多分析各种状态。

代码：

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<string>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<stack>

#include<list>

#include<queue>

#define eps 1e-6

#define INF 0x1f1f1f1f

#define PI acos(-1.0)

#define ll __int64

#define lson l,m,(rt<<1)

#define rson m+1,r,(rt<<1)|1

//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

/*

freopen("data.in","r",stdin);

freopen("data.out","w",stdout);

*/

#define Maxn 1100

//最多只有1000*5

int dp[Maxn][12][12]; //dp[i][x][y]表示处理到了当前i位，且最后两位是x和y的，转到最后的i位所需的最小步数

int a[Maxn],b[Maxn];

char sa[Maxn];

int main()

{

   while(~scanf("%s",sa))

   {

      int n=strlen(sa);

      for(int i=1;i<=n;i++)

         a[i]=sa[i-1]-'0';

      scanf("%s",sa);

      for(int i=1;i<=n;i++)

         b[i]=sa[i-1]-'0';

      memset(dp,INF,sizeof(dp));

      dp[0][0][0]=0;

      for(int i=1;i<=n;i++)

      {

         for(int x=0;x<=9;x++)

         {

            if(i==1&&x) //只有1位的话全部处理为x=0的情况

               continue;

            for(int y=0;y<=9;y++)

            {

               int up=(b[i]-y+10)%10; //当前位一定要达到要求

               int dow=(y-b[i]+10)%10;

               if(i==1) //此时x一定为0

                  dp[i][x][y]=min(up,dow);

               else if(i==2)

               {

                  int xx=0; //i-2位置为0，表示只有一位的情况

                  for(int j=0;j<=up;j++) //正转

                  {

                     int yy=(x+j)%10; //在当前位达到要求时，前面一位最多可以移动up位

                     dp[i][x][y]=min(dp[i][x][y],dp[i-1][xx][yy]+up);

                  }

                  for(int j=0;j<=dow;j++) //反转

                  {

                     int yy=(x-j+10)%10;

                     dp[i][x][y]=min(dp[i][x][y],dp[i-1][xx][yy]+dow);

                  }

               }

               else //枚举 操作第i位up或dow时，第i-1位和第i-2位能够到达的状态

               {

                  for(int j=0;j<=up;j++) //2 3 4 先三个移动2 再后面两个移动1 最后一个再移动1

                     for(int p=j;p<=up;p++) //必须满足第i-1位移动的大于等于第i-2位，

                     {

                        int xx=(a[i-2]+j)%10;

                        int yy=(x+p)%10;

                        dp[i][x][y]=min(dp[i][x][y],dp[i-1][xx][yy]+up);

                     }

                  for(int j=0;j<=dow;j++)

                     for(int p=j;p<=dow;p++)

                     {

                        int xx=((a[i-2]-j)+10)%10;

                        int yy=(x-p+10)%10;

                        dp[i][x][y]=min(dp[i][x][y],dp[i-1][xx][yy]+dow);

                     }

               }

            }

         }

      }

      if(n==1)

         printf("%d\n",dp[1][0][a[1]]);

      else

         printf("%d\n",dp[n][a[n-1]][a[n]]);

   }

   return 0;

}

巴特西

dp hdu-4433 locker

最新文章

热门文章