DP】Seq"/>
【DP】Seq
Description
由于hyf长得实在是太帅了,英俊潇洒,风流倜傥,人见人爱,花见花开,车见车载。有一群MM排队看hyf。每个MM
都有自己独特的风格,由于hyf有着一颗包容的心,所以,什么风格的MM他都喜欢……但是,hyf有一个特别的要求
,他不希望总是看到风格得差不多的MM,更加特别的是,如果两个MM风格完全一样,hyf不会有任何意见。现在,h
yf希望从去看他的MM中,去掉一些MM,从而使得相邻2个MM的风格值的差(绝对值)不为1。自然地,hyf希望去掉
的MM越少越好。
Input
第一行一个整数N;
第2~N+1行N个整数,第i个为ci。表示第i个MM的风格值。
N≤1000 0 ≤ ci ≤ 2000
Output
一个数,表示最少要去掉的MM数。
Sample Input
6 4 2 2 1 1 1
Sample Output
2
分析
常见的做法是用dp[ i ]表示到i为止合法的最大长度。
这道题其实类似LIS。可以叫做最长相邻差不为1子序列
代码
#include<bits/stdc++.h>
using namespace std;
int n;
int a[10010];
int dp[10010];
in
更多推荐
【DP】Seq
发布评论