题解 | #合唱队#

合唱队

http://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4

注意从右边到左边的时候要让j一直在i的左边,这样才会有{有j,无j}的两种状态,此题还有一种方法,二分插入法。

#include <string>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    unsigned N = 0;
    while (cin >> N) {
        vector<unsigned> v;
        int height;

        for (int i = 0; i < N; i++) {
            cin >> height;
            v.push_back(height);

        }
        vector<unsigned> dpleft(N, 0), dpright(N, 0);
        for (int i = 0; i < N; i++) {
            dpleft[i] = 1;
            for (int j = 0; j < i; j++) {
                if (v[i] > v[j])
                    dpleft[i] = max(dpleft[j] + 1, dpleft[i]);
            }
        }//for

        for (int i = N - 1; i >= 0; i--) {
            dpright[i] = 1;
            for (int j = N - 1; j > i; j--) {
                if (v[i] > v[j])
                    dpright[i] = max(dpright[j] + 1, dpright[i]);
            }
        }//for
        int maxnum = 0;
        for (int i = 0; i < N; i++)
            if (maxnum < (dpleft[i] + dpright[i] - 1))
                maxnum = dpleft[i] + dpright[i] - 1;
        cout << N - maxnum << endl;
    }//while



}
全部评论

相关推荐

昨天 13:16
湖南工学院 Java
点赞 评论 收藏
分享
lllllkin:感觉可以精简到一页简历,有些排版感觉不是必须的。 时间线越早的,你自己越熟悉的放前面。描述可以更精简些,一些问题解决感觉可以不用写具体技术栈,卖个关子,等面试官问。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务