一道简单的dp题 --- Greenhouse Effect CodeForces - 269B

题目链接:

https://vjudge.net/problem/36696/origin

题目大意:

要求从1到m升序排列,点可以随意移动,问最少需要移动多少次,

思路:

动态规划

可以推出转移方程为:dp[i] = max(dp[i], dp[j]) && mp[i] >= mp[j]  dp[i]++;

其中,dp[i]为i位置的序数mi前能保留(也就是不移动)的最大种类数。

dp[i]++是因为自己也不能移动自己,得加一。

下面是AC代码:

#include <iostream>
#include <cstdio>
#include <string.h> using namespace std;
const int MX = +;
int mp[MX], dp[MX]; int main()
{
int n, m;
scanf("%d%d", &n, &m);
for(int i = ; i <= n; ++i) //初始化mp数组
{
double x;
scanf("%d%lf", &mp[i], &x);
}
mp[++n] = m+;
for(int i = ; i <= n; ++i)
{
for(int j = ; j < i; ++j)
{
if(mp[i] >= mp[j]) dp[i] = max(dp[j], dp[i]);
}
dp[i]++;
}
printf("%d\n", n-dp[n]);
}

如有疑问,欢迎评论指出!

上一篇:GNU C 与 ANSI C(下)


下一篇:python linux 下开发环境搭建