algorithm - 子序列之和

Question

假设第一个整数是 A，A[i] 等于 A 的第 i 个数字(从 0 开始索引，从右到左)，第二个整数是 B ，B[i] 等于 A 的第 i 个数字B(从 0 开始索引，从右到左)。

A 和 B 的幸运和等于 C，C[i] = max(A[i], B[i])。如果i大于或等于整数的大小，则第i位等于0。

例如，

1. 47和729的幸运和是

   max(7,9)=9
   max(4,2)=4
   max(0,7)=7
   answer = 749
   

2. 同理，W的幸运和=(74,92,477)

   max(4,2) = 4
   max(7,9) = 9
   Lucky sum of 74,92 = 94
   Lucky sum of W=(Lucky sum of (94,477))
   

   这是

   max(4,7)=7
   max(9,7)=9
   max(0,4)=4
   

所以w的幸运和=497。

任务:我们得到一个数组 W，其中包含 n (1<=n<=50) 个整数。

我们必须找到 W 的多个非空子序列，使得这些子序列中整数的幸运和是一个幸运数字(幸运数字 是正整数，其十进制表示仅包含幸运数字 4 和 7。例如，数字 47、744、4 是幸运的，而 5、17、467 则不是。

约束:0 < W[i] < 1e9

例子:

1. W = {4,7}:答案 = 3
2. W = {43, 87 ,44}:答案 = 2

这个问题可以用动态规划来解决吗？

如何在 C++ 中有效地解决这个问题？

Answer 1

这是我能想到的(尚未完成):

使用带有位掩码的DP。我们现在用以下方式表示一个数字:每一位都分为五类:

1. (0) -> 0
2. (1,2,3) -> 1
3. (4) -> 2
4. (5,6) -> 3
5. (7) -> 4
6. (8,9) -> -1

正如我们很容易看到的那样，只要有一个位是 8 或 9，它就永远不会被添加到有效的解决方案中。现在我们用位掩码表示数字，它需要 5^8 .

所以我们让 f[i][s]表示我们可以从 first i numbers 中选择子集的总方式找出号码whose bit-mask is s .

这是我刚刚写的代码......
剩下三件事:

1. 使用__int64或 long long而不是 int对于 f[][] .
2. 使用queue如果我们用 for (i = 0;i < MAXS;i++) 枚举，有很多不可能的状态(即 f[][s]==0)来加速枚举.
3. 使用 f[0..1][MAXS] 来减少内存开销。

示例代码:

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define MAXN 51
#define MAXS 390625 //5^8

using namespace std;

const int exp[] = {1, 5, 25, 125, 625, 3125, 15625, 78125, 390625};
int n;
int w[MAXN];
struct node{
    int i;
    int stat;
    node(int x, int y):i(x),stat(y){}
};
queue<node> q;
__int64 f[MAXN][MAXS];
bool inq[MAXN][MAXS];

int main(){
    //freopen("test.txt","r",stdin);
    memset(f,0,sizeof(f));
    memset(inq,0,sizeof(inq));
    scanf("%d",&n);
    for (int i = 0;i < n;i++) scanf("%d",&w[i]);
    while (!q.empty()) q.pop();
    f[0][0] = 1;
    for (int i = 0;i < n;i++)
        for (int j = 0;j < MAXS;j++)
            if (f[i][j] > 0){
                f[i + 1][j] += f[i][j];
                int stat = j;
                int loc = 0;
                int k = 0;
                for (int p = w[i];p > 0;p /= 10){
                    k = p % 10;
                    if (k <= 0) k = 0;
                        else if (k <= 3) k = 1;
                            else if (k <= 4) k = 2;
                                else if (k <= 6) k = 3;
                                    else if (k <= 7) k = 4;
                                        else k = -1;
                    if (k < 0) break;
                    int bit = stat % exp[loc + 1] / exp[loc];
                    if (k < bit) k = bit;
                    stat = stat - (bit - k) * exp[loc];
                    loc++;
                }
                if (k < 0) continue;
                f[i + 1][stat] += f[i][j];
            }
    int ans = 0;
    for (int i = 0;i < MAXS;i++){
        bool flag = false;
        for (int loc = 7;loc >= 0;loc--){
            int bit = i % exp[loc + 1] / exp[loc];
            if (bit > 0) flag = true;
            if (flag == true && (bit != 2 && bit != 4)){
                flag = false;
                break;
            }
        }
        if (flag == true) ans += f[n][i];
    }
    printf("%d\n",ans);
    return 0;
}