题意：求1-n的n个数字中1出现的个数。
解法:数位dp，dp[pre][now][equa] 记录着第pre位为now，equa表示前边是否有降数字（即后边可不能够任意取，true为没降，true为已降）；常规的记忆化搜索
代码：
/******************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string.h>
//freopen ("in.txt" , "r" , stdin);
using namespace std;#define eps 1e-8
const double pi=acos(-1.0);
typedef long long LL;
const int Max=10100;
const int INF=1000000007;
int fac[10];
void init()
{fac[0]=1;fac[1]=1;for(int i=2; i<10; i++)fac[i]=fac[i-1]*10;
}
char s[20];
int dp[20][20][2];
int n;
int num[20];
int dfs(int pre,int now,int equa)
{if(pre==0)return now==1;if(dp[pre][now][equa]!=-1)return dp[pre][now][equa];int ans=0;if(now==1&&!equa)ans+=fac[pre+1];if(now==1&&equa)ans+=n%fac[pre+1]+1;int en=equa?num[pre-1]:9;for(int i=0;i<=en;i++)ans+=dfs(pre-1,i,equa&&i==num[pre-1]);return dp[pre][now][equa]=ans;
}
int getans(int t)
{int p=0;memset(dp,-1,sizeof dp);while(t){num[p++]=t%10;t/=10;}int ans=0;for(int i=0; i<=num[p-1]; i++){ans+=dfs(p-1,i,i==num[p-1]);}return ans;
}
int main()
{init();while(cin>>n){printf("%d\n",getans(n));}return 0;
}
