题目链接：http://www.bnuoj.com/bnuoj/contest_show.php?
cid=3570#problem/43572
题目大意：
Nono从一開始数数，他每数一个数时会计算这个数中1的个数（如211中有两个1）并对1的个数进行累和。当1的个数之和不小于x时。nono就要起床了。特别须要注意的是，当nono数数达到10000时，nono就会由于数太久而再次睡着……
如今nono定下了x，他想知道他数到多少就须要起床了（或是他能够再睡一觉）。
明显是动态规划问题，通过递推预处理能够比較快的得出。a[i]=a[i-1]+sum一边不断的累加到数i时，1的个数，一边当 i%10==1时，更新a[case]=i,即当x=case时。则须要数数数到多少。
附上代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAX=100001;
int a[MAX];
void init()
{
int cas=1;
for(int i=1;i<MAX;i++)
{
int k=i,sum=0;
while(k)
{
if(k%10==1)
{
sum++;
a[cas++]=i;//关键部分
}
k/=10;
}
a[i]=a[i-1]+sum;
}
}
int main()
{
init();
int T;
while(cin>>T)
{
while(T--)
{
int n;
cin>>n;
if(a[n]<10000)
{
cout<<a[n]<<endl;
}
else
{
cout<<"zzz"<<endl;
}
}
}
return 0;
}