求助dalao,调了好久都没过
  • 板块题目总版
  • 楼主ikun_god
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/12/3 10:31
  • 上次更新2023/12/3 12:17:04
查看原帖
求助dalao,调了好久都没过
996255
ikun_god楼主2023/12/3 10:31

RT

//P1831
#include <bits/stdc++.h>
using namespace std;
long long a[101],dp[50][50][10000],len;
long long dfs(int pos,int pront,int mos,bool limit){
    long long tmp=0;
    if (pos==0){
        mos=0;
        return mos;
    }
    if (mos<0){
        return 0;
    }
    if (!limit && dp[pos][pront][mos]!=-1){
        return dp[pos][pront][mos];
    }
    for (int i=0;i<=(limit?a[pos]:9);i++){
        tmp+=dfs(pos-1,pront,mos+(i*(pos-pront)),limit && (i==(limit?a[pos]:9)));
    }
    if (!limit){
        dp[pos][pront][mos]=tmp;
    }
    return tmp;
}
long long f(long long x){
    len=0;
    long long ans=0;
    memset(dp,-1,sizeof dp);
    memset(a,0,sizeof a);
    while (x){
        a[++len]=x%10;
        x/=10;
    }
    for (int i=1;i<=len;i++){
        ans+=dfs(len,i,0,1);
    }
    return ans;
}
int main(){
    long long x,y;
    cin>>x>>y;
    int l=f(x-1),r=f(y);
    cout<<l<<" "<<r<<" "<<r-l<<endl;
}
2023/12/3 10:31
加载中...