关于数位dp
  • 板块灌水区
  • 楼主ChenZQ
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/5/6 22:30
  • 上次更新2024/5/7 13:31:21
查看原帖
关于数位dp
745358
ChenZQ楼主2024/5/6 22:30

hdu3555 为什么这道题他在数位dp前还要将这个数先+1啊

#include<bits/stdc++.h>
using namespace std;
 
long long dp[65][3];
int a[65];
 
void init()
{
    dp[0][0]=1;
    dp[0][1]=dp[0][2]=0;
    for(int i=1;i<64;i++)
    {
        dp[i][0]=dp[i-1][0]*10-dp[i-1][1];
        dp[i][1]=dp[i-1][0];
        dp[i][2]=dp[i-1][1]+dp[i-1][2]*10;
    }
    return;
 
}
 
long long compute(int len)
{
    long long ans=0;
    int flag=0;
    for(int i=len;i>0;i--)
    {
        ans+=dp[i-1][2]*a[i];                ///第一次计算i=len时,已经囊括了所有不足len位的情况
        if(flag) ans+=dp[i-1][0]*a[i];       ///在之后的计算中,前面所有位都已变成了给定的数位上的最大值
        if(!flag&&a[i]>4) ans+=dp[i-1][1];   ///(这里一定是大于4,大于3的话可能下一位不到9从而多算了)
        if(a[i+1]==4&&a[i]==9) flag=1;       ///所以才会出现判断相邻4、9然后令flag=1的情况
 		cout<<ans<<endl;
    }
    return ans;
}
 
int main()
{
    long long t,temp;
    int num;
    init();
        scanf("%lld",&t);
        int len=0,i=0;
        temp=t+1;              // 就是这里
        while(temp)
        {
            a[++i]=temp%10;
            temp/=10;
            len++;
        }
        for(int i=1;i<=len;i++) cout<<a[i];
        cout<<endl<<endl;
        a[len+1]=0;              //防止后续检测i+1时越界
        printf("%lld\n",compute(len));
}

不加会错

2024/5/6 22:30
加载中...