本文主要是介绍CF 4 D. Mysterious Present，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：Mysterious Present
思路：类似于最长上升子序列，开始的时候自作聪明，以为是长和宽可以旋转的，= =
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
#define maxn 5010
#define inf 0xfffffff
struct node
{int x,y;int no;
}p[maxn];
bool cmp(node a,node b)
{if(a.x==b.x)return a.x<b.x;return a.x<b.x;
}
int dp[maxn];
int main()
{int sx,sy;int n;scanf("%d",&n);scanf("%d%d",&sx,&sy);//if(sx>sy)//swap(sx,sy);for(int i=1;i<=n;i++){scanf("%d%d",&p[i].x,&p[i].y);p[i].no=i;//if(p[i].x>p[i].y)//swap(p[i].x,p[i].y);}sort(p+1,p+n+1,cmp);int ctag=n+1;for(int i=0;i<=n;i++)if(p[i].x>sx&&p[i].y>sy){ctag=i;break;}for(int i=ctag;i<=n;i++)if(p[i].x>sx&&p[i].y>sy)dp[i]=1;elsedp[i]=-inf;for(int i=ctag;i<=n;i++)for(int j=i+1;j<=n;j++)if(p[j].x>p[i].x&&p[j].y>p[i].y&&p[j].x>sx&&p[j].y>sy)dp[j]=max(dp[j],dp[i]+1);int ans=0;for(int i=1;i<=n;i++){//cout<<dp[i]<<endl;ans=max(ans,dp[i]);}deque<int>q;while(!q.empty())q.pop_front();int index=1;for(int i=1;i<=n;i++)if(dp[i]>dp[index]&&p[i].x>sx&&p[i].y>sy)index=i;//cout<<index<<endl;q.push_front(p[index].no);for(int i=index-1;i>=1;i--){if(q.size()==ans)break;if(p[index].x>p[i].x&&p[index].y>p[i].y&&dp[index]==dp[i]+1){index=i;q.push_front(p[i].no);if(q.size()==ans)break;}}cout<<ans<<endl;if(ans){while(q.size()>1)cout<<q.front()<<" ",q.pop_front();cout<<q.front()<<endl;}return 0;
}
这篇关于CF 4 D. Mysterious Present的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
