防御导弹 （C语言代码）

解题思路:

动态规划:寻找最长递减序列

300 250 275 252 200 138 245

建立dp[]数组

用dp【i】来存从第一个到第i个的最长递减数列长度

第一个 300 所以dp[0]=1

第二个 250  250＜300 可以加到300后面，变成300 250，所以dp[1]=2

第三个275   275＞250但275＜300 所以不能加到300 250后面，但可以加到300后面，所以dp[2]=2

……

显然，第i个数能不能加到一个递减数列的末尾的条件是(假设末尾的数为a[j]):a[i]＜a[j]

为了保证求得的dp[i]是最长的递减数列，我们还要增加条件dp[i]<dp[j]+1(dp[i]初值为1)

如果满足上面条件，就让dp[i]=d[j]+1(以此来求得所有dp[])

最后从dp[]数组中求得最大值，就是题目所求

参考代码:

#include <stdio.h>
int main()
{
	int max, i, j, k, a[30], dp[30];

	k = 0;
	while (scanf("%d", &a[k++])!=EOF)
		;

	for (i = 0; i < k; i++) {
		dp[i] = 1;
		for (j = 0; j < i; j++) {
			if (a[j] > a[i] && dp[i] < dp[j] + 1)
				dp[i] = dp[j] + 1;
		}
	}

	max = 0;
	for (i = 1; i < k; i++)
		if (dp[max] < dp[i])
			max = i;

	printf("%d", dp[max]);

	return 0;
}