本题是一道比较简单的DP题目，只不过除了记录子问题的最优解，还需要记录子问题的决策以还原整个路径。
首先我们可以假设所有的?都是0，计算出这个数字模X的余数，设为r。
然后从低位到高位提取出来所有的?，假设一共有m个，其中第i个处于第p[i]位。
我们用bool f[i][j]表示前i个(从低到高)问号是否有选法能使得N模X的余数为j。int a[i][j]表示如果f[i][j] == true，那么第i位最小的选择是0-9哪个数字。
边界条件是f[0][r] = true，递推方程是:
f[i][j] = Vf[i-1][j-d*10^p[i]] | d = 0/1 .. 9 (如果第i个问号是N的首位，则从1开始；否则从0开始)
a[i][j] = 最小的d满足 f[i-1][j-d*10^p[i]] == true
其中V表示多个布尔值的或和。
如果f[m][Y]==true即表示有解，这时依照a[][]数组的值倒推即可得出所有问号的取值。
请教一下各位大佬，我这份代码那里有问题啊？？？
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2e5+25;
int dp[205][maxn],Pow[205],x,y;
char s[205];
int main(){
scanf("%s %d %d",s,&x,&y);
int len = strlen(s);
if(s[0]=='0') {
if(len > 1) puts("No solution");
else if(y == 0) puts("0");
else puts("No solution");
return 0;
}
dp[len][0] = 1; Pow[len] = 1;
for(int i = len-1; ~i; --i){
Pow[i] = Pow[i+1] * 10 % x;
if(s[i] == '?'){
for(int k = 0;k < 9; ++k){
for(int j = 0;j < x; ++j){
if(dp[i+1][j]) dp[i][(k*Pow[i+1]+j)%x] = 1;
}
}
}else{
for(int j = 0;j < x; ++j){
if(dp[i+1][j]) dp[i][(j+(s[i]-'0')*Pow[i+1])%x] = 1;
}
}
}
string ans = ""; int val = 0; bool flag = true;
for(int i = 0;i < len && flag; ++i){
if(s[i] == '?'){
int low = (i == 0)?1:0, vis = 0;
for(int j = low;j < 9; ++j){
if(dp[i+1][(y-(val+j*Pow[i+1])%x+x)%x]){
ans += (char)(j+'0'); vis = 1;
val = (val + j*Pow[i+1])%x;
break;
}
}
if(vis == 0) flag = false;
}
else{
val = (val+(s[i]-'0')*Pow[i+1])%x;
if(dp[i+1][(y-val+x)%x] == 0) flag = false;
else ans += s[i];
}
}
if(flag) cout << ans << '\n';
else puts("No solution");
return 0;
}
请问一下，我的代码那里会有问题啊？？？ **#include
using namespace std; typedef long long LL; const int maxn = 2e5+25; int dp[205][maxn],Pow[205],x,y; char s[205]; int main(){ scanf("%s %d %d",s,&x,&y); int len = strlen(s); if(s[0]=='0') { if(len > 1) puts("No solution"); else if(y == 0) puts("0"); else puts("No solution"); return 0; } dp[len][0] = 1; Pow[len] = 1; for(int i = len-1; ~i; --i){ Pow[i] = Pow[i+1] * 10 % x; if(s[i] == '?'){ for(int k = 0;k < 9; ++k){ for(int j = 0;j < x; ++j){ if(dp[i+1][j]) dp[i][(k*Pow[i+1]+j)%x] = 1; } } }else{ for(int j = 0;j < x; ++j){ if(dp[i+1][j]) dp[i][(j+(s[i]-'0')*Pow[i+1])%x] = 1; } } } string ans = ""; int val = 0; bool flag = true; for(int i = 0;i < len && flag; ++i){ if(s[i] == '?'){ int low = (i == 0)?1:0, vis = 0; for(int j = low;j < 9; ++j){ if(dp[i+1][(y-(val+j*Pow[i+1])%x+x)%x]){ ans += (char)(j+'0'); vis = 1; val = (val + j*Pow[i+1])%x; break; } } if(vis == 0) flag = false; } else{ val = (val+(s[i]-'0')Pow[i+1])%x; if(dp[i+1][(y-val+x)%x] == 0) flag = false; else ans += s[i]; } } if(flag) cout << ans << '\n'; else puts("No solution"); return 0; }*
自己蠢了。。。。。