先上题目：
Humble Numbers
Time Limit: 2000/1000 MS
(Java/Others) Memory Limit: 65536/32768 K
(Java/Others)
Total Submission(s): 14364 Accepted
Submission(s): 6236
Write a program to find and print the nth element in this sequence
题意：求出给定范围里面的因子内只包含1,2,3,5,7的所有数(只需要找前面5842个)。
做法如下：由于第5842个数是2000000000，所以不能从1~2000000000逐个检验是不是符合要求，因此我们可以之直接按顺序构造出这5842个数，打个表保存在数组里面查找就可以了。这里用的思想是DP，方法是在已知的Humble Numbers里面滚动着来生成新的数，这很符合DP的思想，用已知的条件不断从未知中推出更多的已知。用四个变量作为四个指针，从第一个元素开始，求出第一个数与2、3、5、7的积，然后从中求出最小的一个作为新的Humble Numbers，当然有可能会出现一个新的Humble Numbers由2、3、5、7中两个以上的数同时相乘得到，因此在移动指针的时候要判断4次，可能会有指针会在同一次循环里面移动，这样才可以保证不会有相同的数出现。
总的来说这一题的做法对于现在的我来说挺有创造性，更不如说现在的自己因为从前的一时不小心理解错了ACM，现在的下意识里经常都是想一题怎样将模板往上面套，但是明明自己知道这是不对的，还是不自觉地做了起来，大概是这样，自己的思维开始狭窄，所以，现在要改变这种想法，如果ACM的各种问题真的可以直接套模板的话，那就变得没意思了，那就变得跟考试没有区别，那还举办这种比赛有什么用呢？(以上是一时想到的东西，顺便记下来→_→)。
上代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #define MAX 100010 5 #define max(x,y) (x>y ? x : y) 6 using namespace std; 7 8 int dp[MAX][11]; 9 int b[MAX][11]; 10 11 12 13 int main() 14 { 15 int n,t,x,max_t,ans; 16 while(scanf("%d",&n),n){ 17 memset(dp,0,sizeof(dp)); 18 memset(b,0,sizeof(b)); 19 max_t=0; 20 ans=0; 21 for(int i=0;i<n;i++){ 22 scanf("%d %d",&x,&t); 23 b[t][x]++; 24 max_t=max(max_t,t); 25 } 26 27 for(int i=1;i<=max_t;i++){ 28 for(int j=0;j<=10;j++){ 29 int w=dp[i-1][j]; 30 if(j>0) w=max(w,dp[i-1][j-1]); 31 if(j<10) w=max(w,dp[i-1][j+1]); 32 dp[i][j]=w; 33 ans=max(dp[i][j],ans); 34 if(b[i][j] && i>=abs(j-5)){ //在起初的几秒里面移动只限于范围以内 35 dp[i][j]+=b[i][j]; 36 ans=max(dp[i][j],ans); 37 } 38 } 39 } 40 printf("%d\n",ans); 41 } 42 return 0; 43 }