AOJ 895.艰难取舍

175


题目



点击显/隐题目

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
也即可以套用最长上升子序列的模板,改一下判断部分即可

代码


点击显/隐代码
/*/
#define debug
#include <ctime>
//*/
#include <cstdio>
#include <cstring>
#include <iostream>
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;
}
发布评论
  • 点击查看/关闭被识别为广告的评论