题意分析

题目要求计算防御导弹CATCHER在每次测试中最多能拦截的来袭导弹数量。CATCHER的限制条件为：初始可发射到任意高度，但后续只能拦截高度不超过上一枚拦截导弹的目标。输入为多组测试数据，每组包含一系列非负整数（导弹高度），以-1结束；若首个值为-1则终止程序。输出每组测试中CATCHER能拦截的最大导弹数，需按指定格式输出并在测试间留空行。

解题思路

代码采用动态规划求解最长不增子序列（LDS）：1）用数组$arr$存储导弹高度，$dp[i]$表示以第$i$枚导弹结尾的最长不增子序列长度；2）对每个位置$j$，遍历其前所有位置$k$，若$arr[j] \leq arr[k]$且$dp[k]$更大，则更新$dp[j] = dp[k] + 1$；3）最终结果为所有$dp[i]$的最大值。算法时间复杂度为$O(n^2)$，需注意输入处理和边界条件（如首个值为-1时终止）。

#include<stdio.h>
int arr[10010];
int dp[10010];
int main()
{

	int ncase = 1;
	while (1)
	{
		int i = 0;
		int len;
		arr[0] = 0;
		while (arr[i] > -1)
		{
			i++;
			scanf("%d", &arr[i]);
		}
		if (i == 1)
			break;
		for (len = 1; len < i; len++)
			dp[len] = 1;
		len--;
		for (int j = 2; j <= len; j++)
		{
			int temp = 0;
			for (int k = j - 1; k >= 1; k--)
			{
				if (arr[j] < arr[k] && temp < dp[k])
				{
					temp = dp[k];
				}
			}
			if (temp != 0)
				dp[j] = temp + 1;
		}
		int ans = 0;
		for (i = 1; i <= len; i++)
			if (ans < dp[i])
				ans = dp[i];
		printf("Test #%d:\n", ncase++);
		printf("  maximum possible interceptions: %d\n\n", ans);
	}
	return 0;
}