解题思路:
改题目有两个方法,写了简单的那种,还有一种是模仿最长上升子序列的,
注意事项:
注意重置数据就好了
参考代码:
#pragma comment(linker, "/STACK:1024000000, 1024000000")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
struct Rec {
int a,b;
}rec[1010];
int tao[1010][1010];
int dp[1010];
int d(int cur) {
if(dp[cur]) return dp[cur];
dp[cur] = 1;
for(int i = 0; i < n; i++) {
if(tao[cur][i]) {
dp[cur] = max(dp[cur],d(i)+1);
}
}
return dp[cur];
}
int main()
{
// freopen("in.txt","r",stdin);
int t;
scanf("%d",&t);
for(int c = 0; c < t; c++) {
memset(tao,0,sizeof(tao));
memset(dp,0,sizeof(dp));
scanf("%d",&n);
for(int i = 0; i < n; i++) {
scanf("%d%d",&rec[i].a,&rec[i].b);
for(int j = 0; j < i; j++) {
if(rec[i].a < rec[j].a && rec[i].b < rec[j].b || rec[i].a < rec[j].b && rec[i].b < rec[j].a)
tao[j][i] = 1;
else if(rec[i].a > rec[j].a && rec[i].b > rec[j].b || rec[i].a > rec[j].b && rec[i].b > rec[j].a)
tao[i][j] = 1;
}
}
int maxn = -1;
for(int i = 0; i < n; i++) {
if(!dp[i]) maxn = max(maxn,d(i));
}
printf("%d\n",maxn);
}
return 0;
}
0.0分
2 人评分
C语言程序设计教程(第三版)课后习题6.10 (C语言代码)浏览:698 |
WU-字符串比较 (C++代码)浏览:754 |
WU-陶陶摘苹果2 (C++代码)浏览:968 |
三角形 (C++代码)记忆化搜索浏览:1220 |
字符逆序 (C语言代码)浏览:609 |
1024题解浏览:806 |
1071题解浏览:484 |
剪刀石头布 (C语言代码)浏览:1432 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:680 |
C语言程序设计教程(第三版)课后习题5.5 (C语言代码)浏览:446 |