本文主要是介绍hdu5064 Find Sequence 单调性dp,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意:给出一个数组a,之和为M,从中挑选出一些数组成数组b满足两个条件:
(1) b1≤b2≤…≤bt
(2) b2−b1≤b3−b2≤⋯≤bt−bt−1
求最大的t。
分析:a数组排序后,由于M<=(1<<22),所以a数组数字种数不超过3000,dp[i][j]表示以i和j结尾的最长串,dp[i][j]=dp[k][i]+1,dp[i][j]具有单调性,满足dp[i][j]的k一定满足dp[i][j+1],复杂度就降到了n^2。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#define pii pair<ll,int>
#define inf (1ll<<60)
#define ll long long
using namespace std;
const int maxn=100005;
int n,M;
int num[5000000];
int rt[3005];
int dp[3005][3005];
int cnt;
int main()
{int t;scanf("%d",&t);int a;while(t--) {memset(num,0,sizeof(num));scanf("%d%d",&n,&M);for(int i=0;i<n;i++) {scanf("%d",&a);num[a]++;}cnt=0;for(int i=1;i<=M;i++) {if(num[i]) {rt[++cnt]=i;}}memset(dp,0,sizeof(dp));int ans=0;for(int i=1;i<=cnt;i++) {dp[i][i]=num[rt[i]];ans=max(ans,dp[i][i]);}for(int i=1;i<=cnt;i++) {int k=i;int tmp=0;for(int j=i+1;j<=cnt;j++) {while(k && rt[i]-rt[k]<=rt[j]-rt[i]) {tmp=max(tmp,dp[k][i]);k--;}dp[i][j]=tmp+1;ans=max(ans,dp[i][j]);}}printf("%d\n",ans);}return 0;
}
这篇关于hdu5064 Find Sequence 单调性dp的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!