欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

2020牛客多校第六场 (H-Harmony Pairs)

程序员文章站 2022-06-27 17:43:48
题目地址题意: 给出nnn,然后求出从000到nnn有多少个数对,满足第一个数小于第二个数,但是第一个数的各位之和要大于第二个数明显数位DP好亏啊…明明不算难的题没写出来,开场就读到了,然后想不明白状态转移的方式…关于两个数需要满足大小顺序又要满足各位之和的要求,实在理不清,然后去写签到题和别的,就把这个丢了主要是以前写过的所有数位DP都是对于范围内的一种数进行求解,第一次遇到关于数对的求解,有点懵逼…赛中实在想不出来,赛后看学长代码就理解了,我菜死了首先最大为1010010^{100}1010....

2020牛客多校第六场 (H-Harmony Pairs)
题目地址
题意: 给出nn,然后求出从00nn有多少个数对,满足第一个数小于第二个数,但是第一个数的各位之和要大于第二个数

明显数位DP
好亏啊…明明不算难的题没写出来,开场就读到了,然后想不明白状态转移的方式…关于两个数需要满足大小顺序又要满足各位之和的要求,实在理不清,然后去写签到题和别的,就把这个丢了
主要是以前写过的所有数位DP都是对于范围内的一种数进行求解,第一次遇到关于数对的求解,有点懵逼…赛中实在想不出来,赛后看学长代码就理解了,我菜死了
首先最大为1010010^{100},所以最大的数所有位都是9,最小的数就是0,各位之差不会超过1000,所以可以以1000打底来防止负数的出现
开一个数组DP[105][2005][2][2][2]DP[105][2005][2][2][2]
五个位置分别代表
当前搜索到的位置
前面已经搜索出来的各位之差
第一个数最高位此时是否有限制
第二个数最高位此时是否有限制
第二个数在前面是否已经大于了第一个数
然后就是常规的数位DP记忆化搜索了,关于DFSDFS函数的书写是

LL DFS(int pos, int sum, bool lima, bool limb, bool limit) {
    if(pos < 0) {
        return sum > base;
    }
    if(DP[pos][sum][lima][limb][limit] != -1) {
        return DP[pos][sum][lima][limb][limit];
    }
    int up1 = lima ? str[pos] - '0' : 9;
    int up2 = limb ? str[pos] - '0' : 9;
    LL res = 0;
    for(int i = 0; i <= up1; ++ i) {
        for(int j = 0; j <= up2; ++ j) {
            if(!limit && i > j) {
                continue;
            }
            res += DFS(pos - 1, sum + i - j, lima && i == up1, limb && j == up2, limit || j > i);
            res %= mod;
        }
    }
    return DP[pos][sum][lima][limb][limit] = res;
}

如果遍历完了(pos<0),就直接判断此时搜索出来的第一个数与第二个数之差,大于1000则代表大于(初始为1000),反之则不符合条件
同时limitlimit代表前面是否第二个数已经大于第一个数,如果还没严格大于,那么这一位就不能进行i>ji>j的操作,也就是

if(!limit && i > j) continue;

然后就很常规的数位DP了

ps:ps:
从学长那学到一个数位DP的技巧,我一直都是记忆化搜索的时候先判断是否有limitlimit,如果有则不进行记忆化,但是学长是单独开了一维状态代表是否有限制,这样每次都是记忆化搜索,空间换取时间更多了,学到了

全部代码是

#include <bits/stdc++.h>
using namespace std;
typedef long long  LL;
const LL mod = 1e9 + 7;
const int base = 1000;
string str;
LL DP[105][2005][2][2][2];
int len;
LL DFS(int pos, int sum, bool lima, bool limb, bool limit) {
    if(pos < 0) {
        return sum > base;
    }
    if(DP[pos][sum][lima][limb][limit] != -1) {
        return DP[pos][sum][lima][limb][limit];
    }
    int up1 = lima ? str[pos] - '0' : 9;
    int up2 = limb ? str[pos] - '0' : 9;
    LL res = 0;
    for(int i = 0; i <= up1; ++ i) {
        for(int j = 0; j <= up2; ++ j) {
            if(!limit && i > j) {
                continue;
            }
            res += DFS(pos - 1, sum + i - j, lima && i == up1, limb && j == up2, limit || j > i);
            res %= mod;
        }
    }
    return DP[pos][sum][lima][limb][limit] = res;
}
int main () {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    memset(DP, -1, sizeof(DP));
    cin >> str;
    len = str.size();
    int L = 0, R = len - 1;
    while(L < R) {
        swap(str[L ++], str[R --]);
    }
    
    cout << DFS(len - 1, base, 1, 1, 0) << endl;
    return 0;
}

本文地址:https://blog.csdn.net/leoxe/article/details/107620745

相关标签: 多校