Dynamic planning -- expansion topics

1. Longest ascending subsequence

Interceptor missile issue

1010. Interceptor missile

For a sequence , seek At least how many ascending sequences can cover

p[i] It means the first one i The maximum number of ascending sequences ,p[i]<p[i+1]

Each time a sequence larger than the maximum number is found , Then update the maximum number

If you can't find it , Just restart a new ascending sequence

for(int i=1;i<=n;i++)
{
	int k=0;
	while(k<cnt&&p[k]<a[i]) k++;
	p[k]=a[i];
	if(k>=cnt) cnt++;
}
cout<<res<<endl<<cnt;

Missile intercept plus

187. Missile defense system - AcWing Question bank

The interception sequence can be strictly increasing or decreasing , Ask how many can be covered

Put each number on the rise / Descending sequence