锐客网

  1. 首页 > it技术 > >

《随机题库训练10》|《随机题库训练10》 A（）

【《随机题库训练10》|《随机题库训练10》 A（）】最长上升子序列的变形.
思路：
很明显,对于i,j位置满足的大小关系,长大于长,宽大于宽,肯定能满足的几率会高一些.
那么只需要取长的作为长,短的作为宽。排序之后,再跑一次最长上升子序列就行了.
复杂度:O(n^2).

#include using namespace std; typedef long long LL; typedef pair pii; const int N = 105; const int Mod = 1e9+7; #define pi acos(-1) #define INF 1e8 #define INM INT_MIN #define pb(a)push_back(a) #define mk(a,b) make_pair(a,b) #define dbg(x) cout << "now this num is " << x << endl; #define met0(axx) memset(axx,0,sizeof(axx)); #define metf(axx) memset(axx,-1,sizeof(axx)); #define sd(ax) scanf("%d",&ax) #define sld(ax) scanf("%lld",&ax) #define sldd(ax,bx) scanf("%lld %lld",&ax,&bx) #define sdd(ax,bx) scanf("%d %d",&ax,&bx) #define sddd(ax,bx,cx) scanf("%d %d %d",&ax,&bx,&cx) #define sfd(ax) scanf("%lf",&ax) #define sfdd(ax,bx) scanf("%lf %lf",&ax,&bx) #define pr(a) printf("%d\n",a) #define plr(a) printf("%lld\n",a) int dp[1005]; struct Node { int x,y; }p[1005]; bool cmp(Node a,Node b) { if(a.x == b.x) return a.y < b.y; return a.x < b.x; } int main() { int t; sd(t); while(t--) { met0(dp); int n; sd(n); for(int i=1; i<=n; ++i) { int x,y; sdd(x,y); p[i].x = max(x,y),p[i].y = min(x,y); } sort(p+1,p+n+1,cmp); int ans = 1; for(int i=1; i<=n; ++i) { dp[i] = 1; //在这忘了,给我卡住了..,如果不初始化为1,那么如果这次循环找不到,dp[i]就会 = 0,那么会影响后面的查找 for(int j=1; j

    推荐阅读


    上一篇：《随机题库练习10》G

    下一篇：属于谁的座位