vijos1098

maksyuki 发表于 oj 分类，标签: DP-线性DP

12 9月 2015

描述

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。

合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

格式

输入格式

输入的第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。

输出格式

输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

样例1

样例输入1[复制]

8186 186 150 200 160 130 197 220

样例输出1[复制]

限制

每个测试点1s

来源

NOIp 2004

题目类型：线性DP

算法分析：求解最长递增子序列和最长递减子序列的长度，然后枚举每一个位置i，找到分别以i为结尾和开始的最长递增子序列的长度和递减子序列的长度之和(自减1)的最大值maxval，最后直接用N减去maxval即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 100 + 1666;

int n, dp1[maxn], dp2[maxn], ans[maxn];

int LIS ()
{
    int maxval = -INF;
    memset (dp1, 0, sizeof (dp1));

    for (int i = 0; i < n; i++)
    {
        int tempmax = 0;
        for (int j = 0; j < i; j++)
            if (ans[i] > ans[j] && tempmax < dp1[j])
                tempmax = dp1[j];

        dp1[i] = tempmax + 1;
        maxval = max (maxval, dp1[i]);
    }

return maxval;
}

int LDS ()
{
    int maxval = -INF;
    memset (dp2, 0, sizeof (dp2));

    for (int i = n - 1; i >= 0; i--)
    {
        int tempmax = 0;
        for (int j = n - 1; j > i; j--)
            if (ans[i] > ans[j] && tempmax < dp2[j])
                tempmax = dp2[j];

        dp2[i] = tempmax + 1;
        maxval = max (maxval, dp2[i]);
    }

return maxval;
}

int main()
{
//   ifstream cin ("aaa.txt");

    cin >> n;
    for (int i = 0; i < n; i++)
        cin>> ans[i];

    LIS ();
    LDS ();

    int maxval = -INF;
    for (int i = 0; i < n; i++)
        maxval = max (maxval, dp1[i] + dp2[i] - 1);

    cout << n - maxval << endl;

return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 100 + 1666;

int n, dp1[maxn], dp2[maxn], ans[maxn];

int LIS ()

{

int maxval = -INF;

memset (dp1, 0, sizeof (dp1));

for (int i = 0; i < n; i++)

{

int tempmax = 0;

for (int j = 0; j < i; j++)

if (ans[i] > ans[j] && tempmax < dp1[j])

tempmax = dp1[j];

dp1[i] = tempmax + 1;

maxval = max (maxval, dp1[i]);

}

return maxval;

}

int LDS ()

{

int maxval = -INF;

memset (dp2, 0, sizeof (dp2));

for (int i = n - 1; i >= 0; i--)

{

int tempmax = 0;

for (int j = n - 1; j > i; j--)

if (ans[i] > ans[j] && tempmax < dp2[j])

tempmax = dp2[j];

dp2[i] = tempmax + 1;

maxval = max (maxval, dp2[i]);

}

return maxval;

}

int main()

{

// ifstream cin ("aaa.txt");

cin >> n;

for (int i = 0; i < n; i++)

cin>> ans[i];

LIS ();

LDS ();

int maxval = -INF;

for (int i = 0; i < n; i++)

maxval = max (maxval, dp1[i] + dp2[i] - 1);

cout << n - maxval << endl;

return 0;

}

zoj3609

vijos1165

一	二	三	四	五	六	日
« 6月
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

超客的水墨烟雨

vijos1098

描述

格式

输入格式

输出格式

样例1

样例输入1[复制]

样例输出1[复制]

限制

来源

分类目录

标签云

书签

近期评论