1049 Counting Ones (30 分)

数位DP模板题。

状态表示：
(f[len][cnt])：表示当前为len位，且当前已统计的(1)的个数为cnt个。

注意点：
一开始把(f)数组表示成一维了，实际上搜索时每层的状态是个三维向量((len,cnt,limit))，limit可以不记录在数组中，但len和cnt是一定要记录在数组当中的。

int f[15][15];
int a[15];
int n;

int dfs(int len,int cnt,bool limit)
{
    if(len == 0) return cnt;
    if(!limit && ~f[len][cnt]) return f[len][cnt];

    int num=limit?a[len-1]:9;
    int res=0;
    for(int i=0;i<=num;i++)
    {
        res+=dfs(len-1,cnt+(i==1),limit&&i==num);
    }

    if(!limit) f[len][cnt]=res;
    return res;
}

int dp(int n)
{
    int len=0;
    while(n)
    {
        a[len++]=n%10;
        n/=10;
    }
    return dfs(len,0,1);
}

int main()
{
    memset(f,-1,sizeof f);

    cin>>n;

    cout<<dp(n)<<endl;
    //system("pause");
    return 0;
}