群晖WordPress绑定域名,开鲁网站seo不用下载,医院 网站建设 新闻,开网站平台需要多少钱题目描述 有一条横贯东西的大河#xff0c;河有笔直的南北两岸#xff0c;岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸#xff0c;而且不同城市的友好城市不相同。每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市#xff0c;但… 题目描述 有一条横贯东西的大河河有笔直的南北两岸岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸而且不同城市的友好城市不相同。每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市但是由于河上雾太大政府决定避免任意两条航道交叉以避免事故。编程帮助政府做出一些批准和拒绝申请的决定使得在保证任意两条航道不相交的情况下被批准的申请尽量多。 输入输出格式 输入格式 第1行一个整数N表示城市数。 第2行到第n1行每行两个整数中间用一个空格隔开分别表示南岸和北岸的一对友好城市的坐标。 输出格式 仅一行输出一个整数表示政府所能批准的最多申请数。 输入输出样例 输入样例#1 复制 7
22 4
2 6
10 3
15 12
9 8
17 17
4 2 输出样例#1 复制 4 说明 50% 1N5000,0xi10000 100% 1N2e5,0xi1e6 首先想的是二维 因为爆栈 n^2 #include bits/stdc.h
using namespace std;
typedef long long ll;
#define inf 2147483647
const ll INF 0x3f3f3f3f3f3f3f3fll;
#define ri register int
template class T inline T min(T a, T b, T c)
{return min(min(a, b), c);
}
template class T inline T max(T a, T b, T c)
{return max(max(a, b), c);
}
template class T inline T min(T a, T b, T c, T d)
{return min(min(a, b), min(c, d));
}
template class T inline T max(T a, T b, T c, T d)
{return max(max(a, b), max(c, d));
}
#define scanf1(x) scanf(%d, x)
#define scanf2(x, y) scanf(%d%d, x, y)
#define scanf3(x, y, z) scanf(%d%d%d, x, y, z)
#define scanf4(x, y, z, X) scanf(%d%d%d%d, x, y, z, X)
#define pi acos(-1)
#define me(x, y) memset(x, y, sizeof(x));
#define For(i, a, b) for (int i a; i b; i)
#define FFor(i, a, b) for (int i a; i b; i--)
#define bug printf(***********\n);
#define mp make_pair
#define pb push_back
const int maxn 10005;
// name*******************************
int t[5005];//映射
struct pos
{int a,b;
} p[5005];
int dp[5005][5005];
int ans0;
int n;
// function******************************
bool cmp(pos x,pos y)
{return x.ay.a;
}
//***************************************
int main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);
// freopen(test.txt, r, stdin);// freopen(outout.txt,w,stdout);cinn;For(i,1,n){cinp[i].ap[i].b;}sort(p1,p1n,cmp);For(i,1,n){dp[i][i]max(dp[i][i],1);For(j,1,i){dp[i1][j]dp[i][j];if(p[i1].bp[j].b)dp[i1][i1]max(dp[i1][i1],dp[i][j]1);ansmax(ans,dp[i1][j],dp[i1][i1]);}}coutans;return 0;
} RETLE 压成一维交 复杂度太大 TLE #include bits/stdc.h
using namespace std;
typedef long long ll;
#define inf 2147483647
const ll INF 0x3f3f3f3f3f3f3f3fll;
#define ri register int
template class T inline T min(T a, T b, T c)
{return min(min(a, b), c);
}
template class T inline T max(T a, T b, T c)
{return max(max(a, b), c);
}
template class T inline T min(T a, T b, T c, T d)
{return min(min(a, b), min(c, d));
}
template class T inline T max(T a, T b, T c, T d)
{return max(max(a, b), max(c, d));
}
#define scanf1(x) scanf(%d, x)
#define scanf2(x, y) scanf(%d%d, x, y)
#define scanf3(x, y, z) scanf(%d%d%d, x, y, z)
#define scanf4(x, y, z, X) scanf(%d%d%d%d, x, y, z, X)
#define pi acos(-1)
#define me(x, y) memset(x, y, sizeof(x));
#define For(i, a, b) for (int i a; i b; i)
#define FFor(i, a, b) for (int i a; i b; i--)
#define bug printf(***********\n);
#define mp make_pair
#define pb push_back
const int maxn 10005;
// name*******************************
struct pos
{int a,b;
} p[200005];
int dp[200005];
int ans0;
int n;
// function******************************
bool cmp(pos x,pos y)
{return x.ay.a;
}
//***************************************
int main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);
// freopen(test.txt, r, stdin);// freopen(outout.txt,w,stdout);cinn;For(i,1,n){scanf(%d %d,p[i].a,p[i].b);}sort(p1,p1n,cmp);For(i,0,n)dp[i]1;For(i,1,n){For(j,i1,n){if(p[j].bp[i].b)dp[j]max(dp[j],dp[i]1);}ansmax(ans,dp[i]);}coutans;return 0;
} TLE 最后还是看题解发现原来是 最长上升子序列长度nlogn #includebits/stdc.h
using namespace std;
#define For(i,a,b) for(int ia;ib;i)
#define FFor(i,a,b) for(int ia;ib;i--)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mod 100000000
#define maxn 200005
#define inf 0x3f3f3f3fstruct node
{int a,b;
} p[maxn];
int f[maxn];
int n;
bool cmp(node x,node y)
{return x.ay.a;
}
int s[maxn];
int top0;int main()
{cinn;For(i,1,n){cinp[i].ap[i].b;}sort(p1,p1n,cmp);For(i,1,n){if(s[top]p[i].b){s[top]p[i].b;}else{s[lower_bound(s1,stop1,p[i].b)-s]p[i].b;}}couttop;return 0;
} 转载于:https://www.cnblogs.com/planche/p/8627402.html
