题目

{% 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
{% endfold %}

题解

从一群人中,删除最少的人,使相邻人的距离不为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 %}