题目
{% 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 %}