dp hdu-4433 locker
题目大意:
给两个长度相等的数字串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做的比较少,以后多分析各种状态。
代码:
<SPAN style="FONT-SIZE: 14px">#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; } </SPAN>
补充:软件开发 , C++ ,