本文主要是介绍2147: Digit，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
看到题目首先想到了数位dp
观察发现，从低位向高位很好推.
令fijkg表示第i个位置，进位值为j 数位和为k 乘d后数位和为g得情况是否成立...
稍微算一算100 * 10 * 1000 * 1000肯定爆掉了...
考虑优化，令fijk表示能凑成进位值为i 数位和为j 乘d后数位和为k最短得长度...
那么这样复杂度就在1000w 可以接受...
因为要保证得到得数是最小得情况,那么只能从高位到低位枚举。
而且每次选出来的值均对原本乘积和得值有影响，那么还要更新一下...
理论上来说不是很难，但是本沙茶还是写了一天...
c++代码如下：
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <ctime>
#include <cstring>
#include <iostream>
#include <algorithm>
#define debug(x) cout<<#x<<" = "<<x<<endl;
#define lowbit(x) x&(-x)
#define PA pair<int, int>
#define MK make_pair
#define rep(i,x,y) for(register int i = x; i <= y; ++ i)
#define repd(i,x,y) for(register int i = x; i >= y; -- i)
using namespace std;
typedef long long ll;
template<typename T>inline void read(T&x)
{x = 0;char c;int sign = 1;do { c = getchar(); if(c == '-') sign = -1; }while(!isdigit(c));do { x = x * 10 + c - '0'; c = getchar(); }while(isdigit(c));x *= sign;
}int n,s1,s2,d;
int f[10][901][910],nw[101],t[101];
struct Str { int lst,num1,num2; };inline void bfs()
{queue<Str>q; q.push((Str){0,0,0});f[0][0][0] = 0;while(!q.empty()){Str a = q.front();q.pop();rep(i,0,9) if(a.num1 + i <= s1 && a.num2 + (i*d + a.lst)%10 <= s2 && f[(a.lst + i*d)/10][a.num1 + i][a.num2 + (i*d + a.lst)%10] > f[a.lst][a.num1][a.num2] + 1){f[(a.lst + i*d)/10][a.num1 + i][a.num2 + (i*d + a.lst)%10] = f[a.lst][a.num1][a.num2] + 1; q.push((Str){(a.lst + i*d)/10,a.num1 + i,a.num2 + (i*d + a.lst)%10});}}
}
void get(int now,int s1,int p)
{if(now == n + 1) exit(0);rep(k,0,9){rep(j,0,9){int q = now,z = p;t[now] = k*d + j;while(t[q] + nw[q] >= 10){t[q - 1] = (t[q] + nw[q]) / 10;t[q] = (t[q] + nw[q]) %10;z += t[q] - nw[q];--q;}z += t[q];if(s1 >= k && s2 >= z && f[j][s1 - k][s2 - z] + now <= n){q = now;nw[q] = k*d; p += nw[q]; while(nw[q] >= 10){p -= nw[q - 1] + nw[q];nw[q - 1] += nw[q]/10;nw[q] %= 10;p += nw[q - 1] + nw[q];--q;}printf("%d",k);get(now + 1,s1 - k,p);}}}
}
int main()
{memset(f,0x3f,sizeof f);read(n);read(s1);read(s2);read(d);bfs();int z = 0;rep(i,1,9){rep(j,0,9)if(s1 >= i && s2 - (i*d + j)%10 - (i*d + j)/10 >= 0 && f[j][s1 - i][s2 - (i*d + j)%10 - (i*d + j)/10] < n){z = i;nw[1] = (i * d)%10;nw[0] = (i * d)/10;break;}if(z) break;}if(!z) return puts("-1");cout << z;get(2,s1 - z,nw[1] + nw[0]);return 0;
}这篇关于2147: Digit的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
