1514

시도1.

dp[p][np][npp] : 현재 위치가 p일때 p+1 가 np만큼 움직였고,  p+2가  npp만큼 움직인 상황에서 최소 횟수 p 위치에서 위 또는 아래로 1,2,3개를 같이 움직여서 p위치에 원하는 값을 맞추고 다음 p+1로 움직인다. 하지만 p 위치에서 1개를, 2개를, 3개를 조합해서 돌릴 경우가 존재할 수 있으며 위에는 그 경우의 수를 포함하지 않는다.

해결방법

dp[p][m1][m2][m3] : 위치가 p일때 p,p+1,p+2 위치에 대해 움직임이 m1,m2,m3 일때 최소 이동 횟수 위의 문제를 해결하기 위해 조합을 통해서 문제를 풀수 있게 바로 p+1로 움직이는게 아니라 1~9까지 움직여 보는 것이다.

dp를 적용할 때는 모든 경우의 수를 포함할 수 있는지 꼭 점검해야 겠다.!!(물론 답을 찾기 위해 필요한 것들만)

#include <iostream> 

#include <iterator>

#include <algorithm> 

#include <vector>

#include <list>

#include <map>

#include <set>

#include <queue>

#include <stack>

#include <string>

#include <cmath>

#include <cstdio>

#include <cstring>

using namespace std;

#define MOD 1000000007

#define INF 2147483647

#define LNF 9223372036854775807

int n,in[100],out[100],dp[100][10][10][10],cal[10]={0,1,1,1,2,2,2,1,1,1};

int solve(int p, int m1, int m2, int m3){

if(p==n) return 0;

int &ret = dp[p][m1][m2][m3];

if(ret != -1) return ret;

ret = 100000;

if((in[p]+m1)%10==out[p]) ret=solve(p+1,m2,m3,0);

for(int i=1; i<10; i++){

ret = min(ret, solve(p,(m1+i)%10,m2,m3)+cal[i]);

ret = min(ret, solve(p,(m1+i)%10,(m2+i)%10,m3)+cal[i]);

ret = min(ret, solve(p,(m1+i)%10,(m2+i)%10,(m3+i)%10)+cal[i]);

}

return ret;

}

int main () {

freopen("sample.txt", "r", stdin);

scanf("%d",&n);

char ch[101];

scanf("%s",ch);

for(int i=0;i<n;i++) in[i]=ch[i]-'0';

scanf("%s",ch);

for(int i=0;i<n;i++) out[i]=ch[i]-'0';

memset(dp,-1,sizeof(dp));

printf("%d\n",solve(0,0,0,0));

return 0;

}