/ @@18khV /

记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 58ms 84.418 MiB
#2 Accepted 58ms 84.414 MiB
#3 Accepted 59ms 84.438 MiB
#4 Accepted 61ms 84.43 MiB
#5 Accepted 61ms 84.484 MiB
#6 Accepted 60ms 84.492 MiB
#7 Accepted 61ms 84.41 MiB
#8 Accepted 60ms 84.438 MiB
#9 Accepted 61ms 84.492 MiB
#10 Accepted 61ms 84.418 MiB

代码

#include<iostream>
#include<cstring>
#include<cstdio>
//#include<stdafx.h>VS2017自带头文件,请无视
using namespace std;
int len[11];
int dp[11][100][100][10][10][2];
int max(int a, int b)
{
    return a > b ? a : b;
}
int dfs(int pos, int sum1, int sum2, int Max1, int Max2, int limit, int flag)
{
    if (pos == 0)
    {
        if (sum1 == sum2)return 0;
        if (sum1 > sum2)return sum1 - sum2 <= Max2;
        else return sum2 - sum1 <= Max1;
    }
    if (!limit&&dp[pos][sum1][sum2][Max1][Max2][flag] != -1)return dp[pos][sum1][sum2][Max1][Max2][flag];
    int temp = 0;
    for (int i = 0; i <= 9; i++)
    {
        if (limit&&i > len[pos])break;
        if ((pos & 1) && i > 0 && flag)continue;
        if (pos & 1)temp += dfs(pos - 1, sum1 + i, sum2, flag &&i == 0 ? Max1 : max(Max1, 9 - i), flag? max(Max2, i-1): max(Max2, i), limit&&i == len[pos], flag&&i == 0);
        else temp += dfs(pos - 1, sum1, sum2 + i, flag?max(Max1, i-1):max(Max1,i), flag&&i == 0 ? Max2 : max(Max2, 9 - i), limit&&i == len[pos], flag&&i == 0);
    }
    if (!limit)return dp[pos][sum1][sum2][Max1][Max2][flag] = temp;
    return temp;

}
int calc(int n)
{
    if (n == -1 || n == 0)return 0;
    int cnt=0;
    while (n)
    {
        len[++cnt] = n % 10;
        n = n / 10;
    }
    return dfs(cnt, 0, 0, 0, 0, 1, 1);
}
int main()
{
    memset(dp, -1, sizeof(dp));
    int l, r;
    scanf("%d%d", &l, &r);
    printf("%d", calc(r) - calc(l-1));
  return 0;
}

信息

递交者
类型
递交
题目
P1021 几乎奇偶等和数
题目数据
下载
语言
C++
递交时间
2020-07-28 16:21:48
评测时间
2023-09-09 17:21:23
评测机
分数
100
总耗时
606ms
峰值内存
84.492 MiB