最少拦截系统

8 389 207 155 300 299 170 158 65

2

最长上升子序列的变形。求出最长上升子序列后取最大值就是答案。

#include <stdio.h>
#include <string.h>

int dp[1100];

int main()
{
	int n,a[1100];
	while(~scanf("%d",&n))
	{
		for(int i = 1; i <= n; i++)
			scanf("%d",&a[i]);

		int ans = -1;
		for(int i = 1; i <= n; i++)
		{
			dp[i] = 1;
			for(int j = 1; j < i; j++)
			{
				if(a[i] > a[j] && dp[i] < dp[j]+1)
					dp[i] = dp[j]+1;
			}
			if(ans < dp[i])
				ans = dp[i];
		}
		printf("%d\n",ans);
	}
	return 0;
}

hdu 1257 最少拦截系统

原文：http://blog.csdn.net/u013081425/article/details/19539649