华为OJ-合唱队
描述
计算最少出列多少位同学，使得剩下的同学排成合唱队形
说明：
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足存在i（1<=i<=K）使得
Ti < T2 < ...< Ti-1 < Ti > Ti+1>...>TK
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
知识点
循环
运行时间限制
0M
内存限制
0
输入
整数N
一行整数，空格隔开，N位同学身高
输出
最少需要几位同学出列
样例输入
8 186 186 150 200 160 130 197 200
样例输出
4
楼下的代码重点在于维护了两个数组，res_up【i】保存了序列arr[0]到arr[i]的并且含有arr[i]最长升序的长度 res_down[i]则是从后面向前数的，于是num就表示合唱团包含 i 这个下标参加合唱的人数 OK 差不多就是这样
重点在代码// 合唱队.cpp
#include "stdafx.h"//vs的头文件
#include <iostream>
using namespace std;
int getSubseq_up(int,int [],int *);
int getSubseq_down(int,int [],int *);
int main()
{
int len;
int tmp = 0;
int arr[500];
cin >> len;
for (int i = 0;i < len;i++) {
cin >> arr[i];
}
int res_up[500];
int res_down[500];
getSubseq_up(len, arr, res_up);
getSubseq_down(len,arr,res_down);
//需要知道包含i但不大于i的最长子序列的长度
for (int i = 0;i < len;i++) {
int num = res_up[i] + res_down[i]-1;
if (num > tmp)
tmp = num;
}
cout << len - tmp << endl;
return 0;
}
int getSubseq_up(int len, int arr[],int res[]) {/*这里应用到动态规划的思想（ps 算法导论上面提到dp的p是指表格法，这里确实）
for (int j = 0;j < len;j++) {
res[j] = 1;
for (int k = 0;k < j;k++) {
if (arr[j] > arr[k] && res[j] < (res[k] + 1)) {
res[j] = res[k] + 1;
}
}
}
return 0;
}
int getSubseq_down(int len, int arr[], int res[]) {
for (int j = len-1;j >= 0;j--) {
res[j] = 1;
for (int k = len-1;k > j;k--) {
if (arr[j] > arr[k] && res[j] < (res[k] + 1)) {
res[j] = res[k] + 1;
}
}
}
return 0;
}
#include <iostream> using namespace std;
int getSubseq_up(int,int [],int *);
int getSubseq_down(int,int [],int *);
int main()
{
int len;
int tmp = 0;
int arr[500];
cin >> len;
for (int i = 0;i < len;i++) {
cin >> arr[i];
}
int res_up[500];
int res_down[500];
getSubseq_up(len, arr, res_up);
getSubseq_down(len,arr,res_down);
//需要知道包含i但不大于i的最长子序列的长度
for (int i = 0;i < len;i++) {
int num = res_up[i] + res_down[i]-1;
if (num > tmp)
tmp = num;
}
cout << len - tmp << endl;
return 0;
}
int getSubseq_up(int len, int arr[],int res[]) {/*这里应用到动态规划的思想（ps 算法导论上面提到dp的p是指表格法，这里确实）
for (int j = 0;j < len;j++) {
res[j] = 1;
for (int k = 0;k < j;k++) {
if (arr[j] > arr[k] && res[j] < (res[k] + 1)) {
res[j] = res[k] + 1;
}
}
}
return 0;
}
int getSubseq_down(int len, int arr[], int res[]) {
for (int j = len-1;j >= 0;j--) {
res[j] = 1;
for (int k = len-1;k > j;k--) {
if (arr[j] > arr[k] && res[j] < (res[k] + 1)) {
res[j] = res[k] + 1;
}
}
}
return 0;
}
代码参考了http://blog.csdn.net/xiaoski/article/details/47161009 毕竟新人给自己一点时间