poj3373Changing Digits(dp)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

链接

dfs倒着搜返回的路径不能满足相同的数最多借鉴了下别人的代码。。

先dp出来再倒着标记一下然后正回来一定可以满足了

dp保存的是最小的不相同数

#include <iostream>
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define INF 0xfffffff
int dp[][];
char s[];
int flag,path[],k,m,pp[],f[][];
int main()
{
int i,j,g;
while(scanf("%s%d",s,&m)!=EOF)
{
k = strlen(s);flag=;
memset(f,,sizeof(f));
for(i = ; i <= k ; i++)
for(j = ; j <= m ; j++)
dp[i][j] = INF;
if(k==)
{
printf("%c\n",s[]);
continue;
}
for(i = ; i <= ; i++)
{
if(i==s[]-'')
dp[][i%m] = min(dp[][i%m],);
else
dp[][i%m] = min(dp[][i%m],);
}
for(i = ; i < k ; i++)
for(j = ; j<m ; j++)
{
if(dp[i][j] == INF) continue;
for(g = ; g <= ; g++)
{
int o;
if(g==s[i]-'')
o = ;
else
o = ;
dp[i+][(j*+g)%m] = min(dp[i+][(j*+g)%m],dp[i][j]+o);
}
}
f[k][] = ;
for(i = k- ; i>= ; i--)
for(j = ; j < m ; j++)
{
if(dp[i][j]==INF) continue;
for(g = ; g <= ; g++)
{
int o;
if(g==s[i]-'')
o = ;
else
o = ;
if(dp[i][j]+o==dp[i+][(j*+g)%m]&&f[i+][(j*+g)%m])
{
f[i][j] = ;
}
}
}
int ss;
for(i = ; i < ; i++)
{
int o;
if(i==s[]-'')
o = ;
else
o = ;
if(f[][i%m]&&dp[][i%m]==o)
{
printf("%d",i);
ss = i%m;
break;
}
}
for(i = ; i <= k ;i++)
{
for(g = ; g <= ; g++)
{
int o;
if(g==s[i-]-'')
o = ;
else
o = ;
if(f[i][(ss*+g)%m]&&dp[i][(ss*+g)%m]==dp[i-][ss]+o)
{
printf("%d",g);
ss = (ss*+g)%m;
break;
}
}
}
puts("");
}
return ;
}