C++(clang++ 11.0.1) 解法, 执行用时: 295ms, 内存消耗: 141424K, 提交时间: 2022-12-09 17:23:33

#include <bits/stdc++.h>
using namespace std;

typedef long long i64;
typedef vector<int> vi;
typedef pair<int,int> pii;

template<typename T>
inline T read(){
    T x=0,f=0;char ch=getchar();
    while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return f?-x:x;
}

#define rdi read<int>
#define rdi64 read<i64>
#define fi first
#define se second
#define pb push_back
#define mp make_pair

const int K=110,S=1023;

int k,s,p,d;
bitset<S> f[K][S][10];
int res[K];

int main()
{
    k=rdi(),s=rdi(),p=rdi(),d=rdi();    
    	f[0][0][0][0] = 1; // 定义起始状态合法
	
	// f[i][s][x][p-x], i+1<=k 
	for (int i=0;i < k;i ++ )
	{
		for (int ss=0;ss <= i*9;ss ++ )		// 枚举原数数位和
		{ 
			for (int x=0;x <= 9;x ++ ) 		// 枚举进位 x 
			{
				for (int j=(i==k-1);j <= 9;j ++ ) 	// 枚举放的数 j 
				{
				//	if (!j && i+1 == k) continue ;	// 前导零
					
					/*
						f[i+1][s+j][sum/10][p + sum%10] += f[i][s][x][p];
						最高位以前的0没有意义，所以可以用 bitset 直接异或
						如果不是？那么右移后多出长度<S>的部分会被看做零，这题没有意义，所以可以用bitset优化层 
                    	跳过枚举 p
						假设 sum%10  =3
						对于每一个 p∈[3, S]: f[][][][p] += f[][][][p - 3] 
						(题目给定后数为数不会超过 1000) 
						形如：(左边低位 
						f[p]	0111 0010 0110 0101 1000
						f[p-3]:	___1 0010 0110 0101 1000 000_ 是合法的 
						即 (0111 0010 0110 0101 1000) |= (1001 0011 0010 1100 0000)
							
						只需要考虑是否大于0即可，所以可以直接异或
					*/ 
					
					int sum = x + j * d;
					f[i+1][ss+j][sum/10] |= (f[i][ss][x] << (sum%10));
				}
			}
		}
	}
    
    bool fl=0;
    for(int x=0;x<10;x++)
	{	// 从小到大枚举原数乘d后的最高位 x 
        if(p>=x&&f[k][s][x][p-x]) 
		{
			// "直接" 说明x合法且有解 
			// 第一次找到，则一定由解，则一定最小
			// 为什么一定有解？因为递推是从小到大递推，
			// 如果终点以后解，那么一定可以枚举出路径
			// 除了j，枚举这里就不需要考虑枚举是从小到大还是从大到小了 
			// 因为终点已经确定是最小了 
			
            p-=x, fl=1;
            // 标记找到，p -= x  
            
            // 一定要从最高位开始，逆着推回去 
            for(int i=k; i>=1 ;i --)
			{	
			
			
				/*
					贪心策略 cur 
					从高位到低位，放的j从小到大，枚举
					 最高位肯定不能是零 否则其他可以是0 
				*/
                for(int cur=(i==k);cur<=9;cur++)
				{
                    for(int px=0;px<10;px++) // f[i][s][x][p] 枚举新的 x ，不过这里的是 i-1层 
					{	
						// 枚举f[i-1]的乘d高位进位 px 
						// 计算现在的原数位和 ps 
                        int ps=s-cur,sum=cur*d+px;
                        if(ps<0 || sum/10!=x) continue;
                        
                        int pp=p-sum%10;
                        /*
							因为 f[i+1][s+j][sum/10][p + sum%10] += f[i][s][x][p];
							pp = p - sum%10
						*/ 
                        if(pp<0 || !f[i-1][ps][px][pp]) continue;
                        res[i]=cur,x=px,s=ps,p=pp; 	// 找到一个合法的路径 
                        							// 因为推出 f[i-1] 合法，说明一定有起点
													// 不需要像递归搜索那样需要反悔 
                        goto nxt; 	// 连跳两层循环 
                        			// 枚举下一层 i-1
                    }
                }
                
                nxt:;
            }
            		// 已经找到了一个合法方案，且从小到大枚举高位 
            break; 	// 一定是最小的，故退出枚举最高位x的for循环 
        }
    }
    
    if(!fl)
		puts("-1");
    else // 字符输出 快写 
		for(int i=k;i>=1;i--) putchar(res[i]+'0');
    
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 279ms, 内存消耗: 34444K, 提交时间: 2019-09-06 13:27:43

#include <cstdio>
#include <assert.h>
int K, S, P, D;
bool dp[100][901][102][9];
int main()
{
    scanf("%d%d%d%d", &K, &S, &P, &D);
    if (S > K * 9 || P > K * 9)
        return puts("-1"), 0;
    if (S * D % 9 != P % 9)
        return puts("-1"), 0;
    dp[0][S][P / 9][0] = 1;
    for (int i = 1; i < K; i++)
    {
        int S_low = S - i * 9, P_low = P - i * 9, MODnine;
        if (S_low < 0)
            S_low = 0;
        if (P_low < 0)
            P_low = 0;
        for (int j = S_low; j <= S; j++)
        {
            bool (*DP)[9] = dp[i][j];
            for (int l = 0; l < D; l++)
            {
                MODnine = (j * D + l) % 9;
                for (int k = P_low / 9, realk = k * 9 + MODnine; realk <= P; k++, realk += 9)
                    for (int di = 0; !DP[k][l] && di < 10; di++)
                        if (dp[i - 1][j + (l * 10 + di) / D][(realk + di) / 9][(l * 10 + di) % D])
                            DP[k][l] = 1;
            }
        }
    }
    int head = D;
    while (head < 10 * D && !dp[K - 1][head / D][(head / 10 + head % 10) / 9][head % D])
        head++;
    if (head == 10 * D)
        puts("-1");
    else
    {
        int res = head % D;
        putchar(head / D + 48);
        int I = K - 1, J = head / D, K = head / 10 + head % 10, L = head % D, di;
        int newI, newJ, newK, newL;
        while (I)
        {
            for (di = 0; !dp[I - 1][J + (L * 10 + di) / D][(K + di) / 9][(L * 10 + di) % D]; di++)
                "Nothing to do..";
            putchar((res * 10 + di) / D + 48);
            res = (res * 10 + di) % D;
            newI = I - 1, newJ = J + (L * 10 + di) / D, newK = K + di, newL = (L * 10 + di) % D;
            I = newI, J = newJ, K = newK, L = newL;
        }
        assert(res == 0);
    }
    return 0;
}