sdut 2594
毛线除了泡妹子以外最喜欢的就是玩些无聊的游戏了。他最近又迷上了一个非常无聊的游戏,那就是...跳格子。他在墙边画了许许多多的格子,每次从外面往墙的那边跳,使自己更加靠近墙。
为了增加下游戏的难度,毛线每次跳之前会规定下自己每次能跳几个格子,然后试着让自己在这个限制下最靠近墙。
输入
输入包含多组数据,对于每组测试数据:
第一个给出格子的总数 N(1<=N<=1000000),然后是 M(M<=10),接下来 M 行每行一个数 K(K<=N),表示毛线可以一次跳 K 格。
输出
输出毛线最远可以跳到的地方离墙还有多少个格子。
示例输入
11 3
5
7
8
100 5
81
71
61
51
21
示例输出
1
7
提示
第一组数据,毛线可以跳两次 5 格,这样距墙只有一格
第二组数据,毛线可以先跳 51 格,再跳两次 21 个,这样距墙只有 7 格
1 #include<stdio.h>
2 #include<
string.h>
3 int c[
20],dp[
1000010];
4 int main ()
5 {
6 int n,m;
7 while(~scanf(
"%d %d",&n,&
m))
8 {
9 for(
int i =
0; i < m; i++
)
10 scanf(
"%d",&
c[i]);
11 memset(dp,
0,
sizeof(dp));
12 dp[
0] =
1;
13 for(
int i =
0; i < m; i++
)
14 for(
int j = c[i]; j <= n; j++
) //顺序排列
15 if(dp[j-
c[i]])
16 dp[j] =
1;
17 for(
int i = n; i >=
0; i--
)
18 if(dp[i])
19 {
20 printf(
"%d\n",n-
i);
21 break;
22 }
23 }
24 return 0;
25 }
转载于:https://www.cnblogs.com/LK1994/archive/2013/05/11/3073329.html
相关资源：JAVA上百实例源码以及开源项目
