题目描述

A luxury yacht with 100 passengers on board is sailing on the sea in the twilight. The yacht  is ablaze with lights and there comes out laughers and singing from the hall where an evening party is in full swing. People are singing, dancing and enjoying themselves.

The yacht is equipped with the most advanced navigation and driving system which can all be manipulated by a computer. When the captain notices that there is only gentle breeze and the sea waves are not high, he starts the autopilot. The yacht sails forward smoothly, ploughs the waves. When it’s completely dark, the passengers start to feel a little funny for sudden forward rushes or sudden decelerations or slight swings. The captain immediately walks to the driving platform and switches the autopilot to human manipulation. The yacht returns back to normal and the party restarts. Laughers come back, too.

The captain summons the engineer on board to do a thorough check of the navigation system. It turns out that only the computer is out of order, but the exact failure is still unclear. There is a computer scientist among the passengers who is also invited to the cab to give a hand. He first inputs several groups of data to test the computer. When he inputs 1+2+3, the computer outputs 6, which is exactly right. But when he inputs 4+5+6, the computer outputs 5, which is wrong. Then he inputs 12+13+14, and gets 39, another right answer, while he inputs 14+15+16, and gets 35, another wrong answer. After the test, the computer scientist says smilingly: “the failure is clear now. The computer's adder can not carry." After excluding the failure, the captain restarts the autopilot and the yacht returns back to normal, sailing smoothly on the sea.

The captain and the engineer invite the computer scientist to sit down and have a talk. The computer scientist tells a story as following:

A former mathematician defined a kind of simple addition expression. 
If there is an expression (i) + (i+1) + (i+2), i>=0, when carried out additive operations, no position has a carry, it is called simple addition expression.

For instance, when i equals 0, 0+1+2 is a simple addition expression, meanwhile when i equals 11, 11+12+13 is a simple addition expression, too. Because of that no position has a carry.

However, when i equals 3, 3+4+5 is not a simple addition expression, that is because 3+4+5 equals 12, there is a carried number from unit digit to tens digit. In the same way, when i equals 13, 13+14+15 is not a simple addition expression, either. However, when i equals 112, 112+113+114 is a simple addition expression. Because 112+113+114 equals 339, there is no carry in the process of adding.

when the students have got the definition of simple addition expression, the mathematician puts forward a new question: for a positive integer n, how many simple addition expressions exist when i<n. In addition, i is the first number of a simple addition expression.

when the value of n is large enough, the problem needs to be solved by means of computer.

 

 

输入

There are several test cases, each case takes up a line, there is an integer n (n<10^10).

 

输出

Output the number of all simple addition expressions when i<n.

 

样例输入

复制样例数据

1
2
3
4
10
11

样例输出

1
2
3
3
3
4

题目大意:找出n之前(不包括n)有多少满足i+1+i+2+i没有进位的数

题解思路:

第一次用数位dp,先总结一下这两天来学习数位dp的知识.

1.题目数据很大时,考虑用数位dp

2.题目询问 l-r 内有多少满足要求的数时,考虑数位dp(此时不一定成立)

3.做题时首先列一下符合要求的数与其位数的关系

题解正式开始:

首先我们要知道 如果一个数满足 没有进位会有两种情况 (枚举一下便可知道):

1.个位数 要<=2  (即0 1 2)  PS:3+4+5=12>10

2.其余位数 要<=3 且 此时个位数要<=2  PS :34 35 36个位进位

所以我们用朴素的dp打表方法可以轻松得到状态转移方程,设f(i,j)表示 当前位数为i,最高位为j满足要求的个数,则:

f(i,j)=

1. i==1&&j<=2 f(i,j)=1

2.i>1&&j<=3 f(i,j)=SUM[f(i-1,k)] {0<=k<=9}

我们从最高位向下枚举即可,因为任何一个数都可以拆分 例:1234 =1000 + 200 + 30 +4,具体可以搜一下网上的讲解

代码如下(朴素版本):

#include <bits/stdc++.h>
#define E 2.718
using namespace std;
typedef  long long ll;
const ll INF=0x7f7f7f7f;
const int maxn=1e6+8;
const double eps=1e-10;
const ll mod=1000000007;
ll n,m,f;
ll dp[15][12];//represent first high and count of number
ll save[15];
void restart()
{
    for(int i=0;i<=9;i++)
    {
        if(i<=2) dp[1][i]=1;
        else dp[1][i]=0;
    }
    for(int i=2;i<12;i++)
    {
        for(int k=0;k<=9;k++)
        {
            if(k>3) dp[i][k]=0;
            else
            {
                for(int j=0;j<=9;j++)
                    dp[i][k]+=dp[i-1][j];
            }
        }
    }
}
ll solve(ll x)
{
    ll sum=0,cnt=0;
    while(x)
    {
        save[++cnt]=x%10;
        x/=10;
    }
    for(int i=cnt;i>=1;i--)
    {
        for(int k=0;k<save[i];k++)
        {
            if(i!=1&&k>3) break;
            if(i==1&&k>2) break;
                sum+=dp[i][k];
        }
        if(i>1&&save[i]>3) break;
        if(i==1&&save[i]>2) break;
    }
    return sum;
}
int main()
{
    restart();
    while(~scanf("%lld",&n))
    {
        printf("%lld\n",solve(n));
    }
    return 0;
}

第二种记忆化搜索,首先理解模板代码,然后顺此题改一下即可:

代码如下(记忆化搜索):

#include <bits/stdc++.h>
#define E 2.718
using namespace std;
typedef  long long ll;
const ll INF=0x7f7f7f7f;
const int maxn=1e6+8;
const double eps=1e-10;
const ll mod=1000000007;
ll n,m;
ll dp[20][2];
ll a[20];
ll dfs(int pos,int state,bool limit)
{
    ll sum=0;
    if(pos<1) return 1;
    if(!limit&&dp[pos][state]!=-1) return dp[pos][state];
    int up=(limit?a[pos]:9);
    for(int i=0;i<=up;i++)
    {
        if(pos>1&&i>3) continue;
        if(pos==1&&i>2) continue;
        sum+=dfs(pos-1,pos-1==1,i==up&&limit);
    }
    if(!limit) dp[pos][state]=sum;
    return sum;
}
ll solve(ll x)
{
    ll cnt=0;
    while(x)
    {
        a[++cnt]=x%10;
        x/=10;
    }
    return dfs(cnt,0,true);
}
int main()
{
    memset(dp,-1,sizeof(dp));
    while(~scanf("%lld",&n))
    {
        printf("%lld\n",solve(n-1));
    }
    return 0;
}

总结:

1.所有dp都是在找状态转移方程,数位dp也不例外,搞清楚状态即可

2.第一次接触数位dp,有点生,还需要多练,此后会更新一套数位dp总结,必须要写(flag)

3.再自己感觉一下模板写法