这是一篇最后编辑于 8 年前 的文章，其内容可能与目前实际情况差异较大，请注意甄别
题目
{% fold 点击显/隐题目 %}
Description 由于 lls 长得实在是太帅了，英俊潇洒，风流倜傥，人见人爱，花见花开，车见车载。有一群 MM 排队看 lls。每个 MM 都有自己独特的风格，由于 lls 有着一颗包容的心，所以，什么风格的 MM 他都喜欢……但是，lls 有一个特别的要求，他不希望总是看到风格得差不多的 MM，更加特别的是，如果两个 MM 风格完全一样， lls 不会有任何意见。现在， lls 希望从去看他的 MM 中，去掉一些 MM，从而使得相邻 2 个 MM 的风格值的差（绝对值）不为 1。自然地， lls 希望去掉的 MM 越少越好。
第一行一个整数 N； 第 2~N+1 行 N 个整数，第 i 个为 ci。表示第 i 个 MM 的风格值。
一个数，表示最少要去掉的 MM 数。
6 4 2 2 1 1 1
2 Hint N≤1000,0 ≤ ci ≤ 2000
题解
从一群人中,删除最少的人,使相邻人的距离不为1
可以等价为从一群人中,选择最多的人(子序列),使相邻人的距离不为1
也即可以套用最长上升子序列的模板,改一下判断部分即可
代码
{% fold 点击显/隐代码 %}```cpp 艰难取舍 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
//
#define debug
#include
///
#include
#include
#include
using namespace std;
const int maxn = 1005;
int a[maxn], dp[maxn];
inline int abs(int a){
return a>0?a:-a;
}
int main() {
#ifdef debug
freopen("in.txt", "r", stdin);
int START = clock();
#endif
cin.tie(0);
cin.sync_with_stdio(false);
int n;
while (cin >> n) {
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int Max = 0;
for (int i = 1; i <= n; i++) {
dp[i] = 0;
for (int j = 0; j < i; j++) {
if (abs(a[i] - a[j]) != 1) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
Max = max(Max, dp[i]);
}
cout << n-Max << endl;
}
#ifdef debug
printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;
}
{% endfold %}