「泉七培训 – 郑予凡」雷神领域
此题数据水，各种骗分。。。
二维偏序最长链，两个方向最小值40分。。。
直接统计不同的x，y坐标个数输出最小值70分。。。
正解似乎比较奇怪。。。
懒得解释了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #define inf 0x7fffffff #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,ans; int dp[5005][5005]; int fa[20005],rank[20005]; int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);} void un(int x,int y) { x=find(x);y=find(y); if(rank[x]<rank[y])swap(x,y); fa[y]=x; rank[x]=max(rank[x],rank[y]+1); } int main() { //freopen("field.in","r",stdin); //freopen("field.out","w",stdout); n=read(); for(int i=1;i<=20000;i++)fa[i]=i; for(int i=1;i<=n;i++) { int x=read(),y=read(); un(x,y+10000); } for(int i=1;i<=20000;i++)find(i); for(int i=1;i<=5000;i++) for(int j=1;j<=5000;j++) { if(fa[i]==fa[j+10000]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); ans=max(dp[i][j],ans); } printf("%d",ans); return 0; } |
计数器 9787531
OI 课件=>
OI 课件=>
学长状态转移方程貌似写错了，样例都过不了啊。
不应该是
g[i][j] = max(g[i-1][j], g[i][j-1]);if(p[i] == p[j+10000]) g[i][j]++;
？