题目地址
题意: 给出,然后求出从到有多少个数对,满足第一个数小于第二个数,但是第一个数的各位之和要大于第二个数
明显数位DP
好亏啊…明明不算难的题没写出来,开场就读到了,然后想不明白状态转移的方式…关于两个数需要满足大小顺序又要满足各位之和的要求,实在理不清,然后去写签到题和别的,就把这个丢了
主要是以前写过的所有数位DP都是对于范围内的一种数进行求解,第一次遇到关于数对的求解,有点懵逼…赛中实在想不出来,赛后看学长代码就理解了,我菜死了
首先最大为,所以最大的数所有位都是9,最小的数就是0,各位之差不会超过1000,所以可以以1000打底来防止负数的出现
开一个数组
五个位置分别代表
当前搜索到的位置,
前面已经搜索出来的各位之差,
第一个数最高位此时是否有限制,
第二个数最高位此时是否有限制,
第二个数在前面是否已经大于了第一个数
然后就是常规的数位DP记忆化搜索了,关于函数的书写是
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),反之则不符合条件
同时代表前面是否第二个数已经大于第一个数,如果还没严格大于,那么这一位就不能进行的操作,也就是
if(!limit && i > j) continue;
然后就很常规的数位DP了
从学长那学到一个数位DP的技巧,我一直都是记忆化搜索的时候先判断是否有,如果有则不进行记忆化,但是学长是单独开了一维状态代表是否有限制,这样每次都是记忆化搜索,空间换取时间更多了,学到了
全部代码是
#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
如对本文有疑问, 点击进行留言回复!!
牛客编程巅峰赛S1第6场 - 黄金&钻石&王者题解
纵横字谜的答案 Crossword Answers, ACM/ICPC World Finals 1994, UVa232
HDU - 5880 Family View (AC自动机修改母串)
iOS14Beta3续航怎么样 iOS14Beta3续航能力介绍
iOS14Beta3稳定性怎么样 iOS14Beta3升级建议介绍
网友评论