题解 - Vijos

1

看了一下没人发题解，我发一个我的做法。

#1 Accepted 82ms 6.867 MiB
#2 Accepted 6ms 640.0 KiB
#3 Accepted 5ms 896.0 KiB
#4 Accepted 8ms 1.0 MiB
#5 Accepted 9ms 2.0 MiB
#6 Accepted 9ms 2.875 MiB
#7 Accepted 30ms 3.625 MiB
#8 Accepted 20ms 5.125 MiB
#9 Accepted 24ms 6.125 MiB
#10 Accepted 47ms 6.875 MiB

主要思路是动态规划，我的代码是记忆化搜索。根据长度来设定状态，每个状态记录当下所至少使用的 ADD DEL MOVE。

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>

#define DIGIT_LEN 7
/*
 *     1
 *   2   3
 *     4
 *   5   6
 *     7
 */
int digit[10][DIGIT_LEN] = {
        {1,1,1,0,1,1,1},
        {0,0,1,0,0,1,0},
        {1,0,1,1,1,0,1},
        {1,0,1,1,0,1,1},
        {0,1,1,1,0,1,0},
        {1,1,0,1,0,1,1},
        {1,1,0,1,1,1,1},
        {1,0,1,0,0,1,0},
        {1,1,1,1,1,1,1},
        {1,1,1,1,0,1,1}
};


#define ABS(X) ((X) < 0 ? (-X) : (X))

int p[3], q[3];
class Num;

static Num* fixOneAddr;

class Num {

    //add del move
    int i[3];
public:
    Num() {
        i[0]=i[1]=i[2]=-1;
    }
    Num(int a,int b, int c)  {
        i[0] =a;
        i[1]=b;
        i[2]=c;
    }
    bool isEqual(Num & o) {
        return i[2] == o.i[2] && i[1] == o.i[1] && i[0] == o.i[0];
    }

    //方向并不重要
    bool isDefinitelyBetter(Num& o) {
        return (i[2]) <= (o.i[2])
               && (i[1]) <= (o.i[1]) && (i[0]) <= (o.i[0]);
//        return ABS(i[2]) >= ABS(o.i[2])
//               && ABS(i[1]) >= ABS(o.i[1]) && ABS(i[0]) >= ABS(o.i[0]);
    }

    inline bool isValid() {
        return i[0] >= 0;
    }

    inline bool isMustInvalid() {
        return i[0] == -2;
    }

    inline void markMustInvalid() {
        i[0] = -2;
    }

//    inline bool advance() {
//        if(i[2] > 0) {
//            i[0]++;
//            i[1]++;
//            i[2]--;
//        }
//    }

    inline void fill(int* add, int* del, int* move) {
        *add = i[0];
        *del = i[1];
        *move = i[2];
    }

    int totalCost() {
        int sum = 0;
        for(int j=0;j<3;j++) {
            int t = i[j];
            sum += t * q[j];
            sum += p[j] * (t+1)*t/2;
        }
        return sum;
    }

    void checkIfCanReplace (Num& base, int extra_add, int extra_del, int extra_move) {
        int sum = 0;
        int temp[3] = {extra_add, extra_del, extra_move};
        for(int j=0;j<3;j++) {
            int t = base.i[j] + temp[j];
            sum += t * q[j];
            sum += p[j] * (t+1)*t/2;
        }

        if(i[0] == -1 || totalCost() > sum) {
            for(int j=0;j<3;j++) {
                i[j] = base.i[j] + temp[j];
            }
        }
//      if(this == fixOneAddr) {
//          printf("weird set value\n");
//      }
    }
};
using namespace std;
vector<Num> calcFirst[10][10];

/**
 * n1(old) -> n2(new)
 */
void tellDiff(int n1, int n2, int* more, int* less) {
    int* na1 = digit[n1];
    int* na2 = digit[n2];
    int moreOut = 0;
    int lessOut = 0;
    for(int i=0;i<DIGIT_LEN;i++) {
        if(na1[i] == na2[i]) continue;

        if(na1[i]) moreOut++;
        if(na2[i]) lessOut++;
    }
    *more = moreOut;
    *less = lessOut;
}

void addNum(vector<Num>& v, Num& wantIn) {
    for(int i=0;i<v.size();i++) {
        if(v[i].isEqual(wantIn)) {
            return;
        }
        if(v[i].isDefinitelyBetter(wantIn)) {
            return;
        }
    }
    v.push_back(wantIn);
}

#define LEVEL_LINE 1400
Num (*fn)[2800];
int a1[200], a2[200];

/**
 *  > LEVEL_LINE mean  before 'maxOne' there are more
 *  or                                 there are less
 */

static Num validOne(0,0,0);
//#define MY_DEBUG
#ifdef MY_DEBUG
bool forTest[200][2800];
#endif

Num& getGoodOne(int maxOne, int level) {


    if(maxOne ==-1) {
        static Num fixOne;
        if(level != LEVEL_LINE) {
            return fixOne;
        }
        return validOne;
    }
    Num& cache = fn[maxOne][level];
    if(cache.isMustInvalid()) {
        return cache;
    }
    if(cache.isValid()) {
        return cache;
    }

#ifdef MY_DEBUG
    {
        if(maxOne == 0 && level == 1488) {
            printf("got you\n");
        }
        if(forTest[maxOne][level]) {
            printf("may reEnter for %d %d\n", maxOne, level);
            exit(0);
        }
        forTest[maxOne][level] = true;
//      static int enterCount = 0;
//      enterCount++;
//      if(enterCount % 100 == 0)
//          printf("now enter %d\n", enterCount);
    }
#endif

    int num1 = a1[maxOne], num2 = a2[maxOne];
    vector<Num>& vi = num1 > num2 ? calcFirst[num1][num2] : calcFirst[num2][num1];

    for(int i=0;i<vi.size();i++) {
        Num& preStrategy = vi[i];
        int add, del, move;
        preStrategy.fill(&add, &del, &move);

        if(add >= 0) { //需要 add 意味着缺少, =0 只是为了至少有一个情况
            for(int add_myself=0; add_myself<=add;add_myself++) {
                int needByOther = add - add_myself;
                Num& before = getGoodOne(maxOne-1, level + needByOther);
                if(before.isValid()) {
                    cache.checkIfCanReplace(before, add_myself, del, move + needByOther);
                }
            }
        }
        if(del > 0) {
            for(int del_myself=0; del_myself<=del;del_myself++) {
                int needByOther = del - del_myself;
                Num& before = getGoodOne(maxOne-1, level - needByOther);
                if(before.isValid()) {
                    cache.checkIfCanReplace(before, add, del_myself, move);
                }
            }
        }

        for(;move>0; ) {
            add++;
            del++;
            move--;
            Num& before = getGoodOne(maxOne-1, level);
            if(before.isValid()) {
                cache.checkIfCanReplace(before, add, del, move);
            }
        }
    }

    if(!cache.isValid()) {
        cache.markMustInvalid();
    }
    return cache;
}

void preCalc() {
    fixOneAddr = &validOne;
    for(int i=0;i<10;i++) {
        for(int j=0;j<i;j++) {
            for(int k=0;k<10;k++) {
                int m_i, l_i;
                int m_j, l_j;
                tellDiff(i, k, &m_i, &l_i );
                tellDiff(j, k, &m_j, &l_j );
                int more = m_i+m_j;
                int less = l_i + l_j;

                int common = std::min(more, less);
                Num num(less - common,more - common,common);
                addNum(calcFirst[i][j], num);
            }

            vector<Num>& preBuild = calcFirst[i][j];
            for(int k=0;k<preBuild.size();k++) {
                for(int k2=k+1;k2<preBuild.size();k2++) {
                    if(preBuild[k2].isDefinitelyBetter(preBuild[k])) {
                        preBuild.erase(preBuild.begin() + k);
                        k--;
                        break;
                    }
                }
            }
        }
        calcFirst[i][i].emplace_back(0,0,0);
    }
}

int main() {
    preCalc();

    int n;
    scanf("%d", &n);
    fn = (Num(*)[2800])(malloc(n * sizeof(Num) * 2800));
    memset(fn, -1,n *  sizeof(Num) * 2800);
    getchar();

    for(int i=0;i<n;i++) a1[i] = getchar() - '0';
    getchar();
    for(int i=0;i<n;i++) a2[i] = getchar() - '0';
    getchar();

    for(int i=0;i<3;i++) scanf("%d%d", &p[i], &q[i]);
    Num& ans = getGoodOne(n-1, LEVEL_LINE);
    printf("%d", ans.totalCost());

    return 0;
}

0

tntxst LV 5 @ 4 年前

/*这个解过了题目举的两个例子，但测试一个都没过，很无语不知道为什么*/

#include <stdio.h>

int count(int num) {
int c = 0;
while (num != 0) {
c += num % 2;
num /= 2;
}
return c;
}

int getSevenRepresent(int num) {
switch(num) {
case 0:
return 119; //0b1110111;
case 1:
return 18; //0b0010010;
case 2:
return 93; //0b1011101;
case 3:
return 91; //0b1011011;
case 4:
return 58; //0b0111010;
case 5:
return 107; //0b1101011;
case 6:
return 111; //0b1101111;
case 7:
return 82; //0b1010010;
case 8:
return 127; //0b1111111;
case 9:
return 123; //0b1111011;
default:
fprintf(stderr, "getSevenRepresent: value %d not a digit", num);
return 0;
}
}

void getdiff(int leftNum, int rightNum, int *leftRm, int *leftAdd, int digit) {
int leftDigit, rightDigit;
for (int i=0;i<digit; i++) {
leftDigit = getSevenRepresent(leftNum % 10);
rightDigit = getSevenRepresent(rightNum % 10);
*leftRm += count(leftDigit & ~rightDigit);
*leftAdd += count(~leftDigit & rightDigit);

leftNum /= 10;
rightNum /= 10;
}
}

int main(void) {
int digit = 0;
int leftNum = 0, rightNum = 0;
int p[3], q[3];
scanf("%d", &digit);
scanf("%d", &leftNum);
scanf("%d", &rightNum);
for (int i=0;i<3;i++) {
scanf("%d", &p[i]);
scanf("%d", &q[i]);
}

int leftRm = 0, leftAdd = 0;
getdiff(leftNum, rightNum, &leftRm, &leftAdd, digit);
int result = 0, rm = 1, add = 1, mov = 1;

// printf("leftRm = %d\n", leftRm);
// printf("leftAdd = %d\n", leftAdd);

while (leftRm != 0 || leftAdd != 0) {
int movCost = p[2] * mov + q[2],
addCost = p[0] * add + q[0],
rmCost = p[1] * rm + q[1];

if (movCost < (addCost + rmCost) &&
leftRm != 0 && leftAdd != 0) {
result += (p[2] * mov + q[2]);
leftAdd--;
leftRm--;
mov++;
} else if (leftAdd == 0 || rmCost < addCost) {
result += (p[1] * rm + q[1]);
leftRm--;
rm++;
} else {
result += (p[0] * add + q[0]);
leftAdd--;
add++;
}
// printf("result = %d\n", result);
// printf("leftRm = %d\n", leftRm);
// printf("leftAdd = %d\n", leftAdd);
}
printf("%d", result);
}