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));
}
不加会错