本文主要是介绍AOJ895 艰难取舍【DP】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
Description
由于 lls 长得实在是太帅了，英俊潇洒，风流倜傥，人见人爱，花见花开，车见车载。有一群 MM 排队看 lls。每个 MM 都有自己独特的风格，由于 lls 有着一颗包容的心，所以，什么风格的 MM 他都喜欢……但是，lls 有一个特别的要求，他不希望总是看到风格得差不多的 MM，更加特别的是，如果两个 MM 风格完全一样， lls 不会有任何意见。现在， lls 希望从去看他的 MM 中，去掉一些 MM，从而使得相邻 2 个 MM 的风格值的差（绝对值）不为 1。自然地， lls 希望去掉的 MM 越少越好。
Input
第一行一个整数 N；
第 2~N+1 行 N 个整数，第 i 个为 ci。表示第 i 个 MM 的风格值。
Output
一个数，表示最少要去掉的 MM 数。
Sample Input
6
4
2
2
1
1
1
Sample Output
2
Hint
N≤1000,0 ≤ ci ≤ 2000
大致思路：
问需要减去多少个人，那么可以转化为最多有多少个人满足要求。
可以利用DP的思想求解：
dp[i] 代表前i个人中最多留下的人数。
则状态转移方程为：
for(int i=1;i<=n;++i)for(int j=0;j<i;++j)if(abs(a[i]-a[j])!=1)//表示符合条件的人dp[i]=max(dp[i],dp[j]+1);//取最优代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=10010;
int a[maxn],dp[maxn];
int main()
{ios::sync_with_stdio(false);//freopen("in.txt","r",stdin);int n,ans=0;cin>>n;for(int i=1;i<=n;++i)cin>>a[i];memset(dp,0,sizeof(dp));for(int i=1;i<=n;++i)for(int j=0;j<i;++j)if(abs(a[i]-a[j])!=1)dp[i]=max(dp[i],dp[j]+1);for(int i=1;i<=n;++i)//取人数最多的情况ans=max(dp[i],ans);cout<<n-ans<<endl;return 0;
}
这篇关于AOJ895 艰难取舍【DP】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
