线段覆盖

线段覆盖

关注
发信
关注(28)粉丝(399)

CodeVS 线段覆盖1~5

 #include <bits/stdc++.h>

 using namespace std;

 const int Maxn=;

 struct Info{int l,r;}P[Maxn];

 int n,Cnt,F[Maxn];

 map<int,int> M;

 inline bool Cmp(Info A,Info B) {return A.r<B.r;}

 inline int Max(int x,int y) {return x>y?x:y;}

 inline void Swap(int &x,int &y) {int t=x;x=y;y=t;}

 int main()

 {

     scanf("%d",&n); Cnt=;

     for (int i=;i<=n;i++)

     {

         scanf("%d%d",&P[i].l,&P[i].r);

         if (P[i].l>P[i].r) Swap(P[i].l,P[i].r);

         M[P[i].l]=,M[P[i].r]=;

     }

     for (map<int,int>::iterator it=M.begin();it!=M.end();it++) it->second=++Cnt;

     for (int i=;i<=n;i++) P[i].l=M[P[i].l],P[i].r=M[P[i].r];

     sort(P+,P+n+,Cmp); int j=;

     for (int i=;i<=Cnt;i++)

     {

         while (j<=n && P[j].r==i)

         {

             F[i]=Max(F[i],F[P[j].l]+);

             j++;

         }

         F[i]=Max(F[i],F[i-]);

     }

     printf("%d\n",F[Cnt]);

     return ;

 }

线段覆盖1

 #include <bits/stdc++.h>

 using namespace std;

 const int Maxn=;

 struct Info{int l,r;}P[Maxn];

 int n,Cnt,F[Maxn];

 map<int,int> M;

 inline bool Cmp(Info A,Info B) {return A.r<B.r;}

 inline int Max(int x,int y) {return x>y?x:y;}

 inline void Swap(int &x,int &y) {int t=x;x=y;y=t;}

 int main()

 {

     scanf("%d",&n); Cnt=;

     for (int i=;i<=n;i++)

     {

         scanf("%d%d",&P[i].l,&P[i].r);

         if (P[i].l>P[i].r) Swap(P[i].l,P[i].r);

         M[P[i].l]=,M[P[i].r]=;

     }

     for (map<int,int>::iterator it=M.begin();it!=M.end();it++) it->second=++Cnt;

     for (int i=;i<=n;i++) P[i].l=M[P[i].l],P[i].r=M[P[i].r];

     sort(P+,P+n+,Cmp); int j=;

     for (int i=;i<=Cnt;i++)

     {

         while (j<=n && P[j].r==i)

         {

             F[i]=Max(F[i],F[P[j].l]+);

             j++;

         }

         F[i]=Max(F[i],F[i-]);

     }

     printf("%d\n",F[Cnt]);

     return ;

 }

线段覆盖2

 #include <bits/stdc++.h>

 using namespace std;

 const int Maxn=;

 struct Info{int l,r,w;}P[Maxn];

 int n,Cnt,F[Maxn];

 map<int,int> M;

 inline bool Cmp(Info A,Info B) {return A.r<B.r;}

 inline int Max(int x,int y) {return x>y?x:y;}

 inline void Swap(int &x,int &y) {int t=x;x=y;y=t;}

 int main()

 {

     scanf("%d",&n); Cnt=;

     for (int i=;i<=n;i++)

     {

         scanf("%d%d%d",&P[i].l,&P[i].r,&P[i].w);

         if (P[i].l>P[i].r) Swap(P[i].l,P[i].r);

         M[P[i].l]=,M[P[i].r]=;

     }

     for (map<int,int>::iterator it=M.begin();it!=M.end();it++) it->second=++Cnt;

     for (int i=;i<=n;i++) P[i].l=M[P[i].l],P[i].r=M[P[i].r];

     sort(P+,P+n+,Cmp); int j=;

     for (int i=;i<=Cnt;i++)

     {

         while (j<=n && P[j].r==i)

         {

             F[i]=Max(F[i],F[P[j].l]+P[j].w);

             j++;

         }

         F[i]=Max(F[i],F[i-]);

     }

     printf("%d\n",F[Cnt]);

     return ;

 }

线段覆盖3

 #include <bits/stdc++.h>

 #define LL long long

 using namespace std;

 const int Maxn=;

 const int Inf=0x3f3f3f3f;

 struct Info{int l,r,w;}P[Maxn];

 int n,Cnt,a[Maxn<<];

 LL F[];

 inline bool Cmp(Info A,Info B) {return A.r<B.r;}

 inline int Min(int x,int y) {return x>y?y:x;}

 inline LL Max(LL x,LL y) {return x>y?x:y;}

 inline void Swap(int &x,int &y) {int t=x;x=y;y=t;}

 inline void Get_Int(int &x)

 {

     x=; register char ch=getchar(); int f=;

     while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

     while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();} x*=f;

 }

 int main()

 {

     Get_Int(n);

     for (int i=;i<=n;i++)

     {

         Get_Int(P[i].l),Get_Int(P[i].r),Get_Int(P[i].w);

         if (P[i].l>P[i].r) Swap(P[i].l,P[i].r);

         a[i*-]=P[i].l,a[i*]=P[i].r;

     }

     sort(a+,a+n*+); Cnt=;

     for (int i=;i<=*n;i++) if (a[i]!=a[Cnt]) a[++Cnt]=a[i];

     for (int i=;i<=n;i++) P[i].l=lower_bound(a+,a+Cnt+,P[i].l)-a,P[i].r=lower_bound(a+,a+Cnt+,P[i].r)-a;

     sort(P+,P+n+,Cmp); int j=;

     for (int i=;i<=Cnt;i++)

     {

         while (j<=n && P[j].r==i)

         {

             F[i]=Max(F[i],F[P[j].l]+(LL)P[j].w);

             j++;

         }

         F[i]=Max(F[i],F[i-]);

     }

     printf("%lld\n",F[Cnt]);

     return ;

 }

线段覆盖4

 #include <bits/stdc++.h>

 #define LL long long

 using namespace std;

 const int Maxn=;

 const int Inf=0x3f3f3f3f;

 struct Info{int l,r,w;}P[Maxn];

 int n,Cnt,a[Maxn<<];

 LL F[Maxn<<];

 inline bool Cmp(Info A,Info B) {return A.r<B.r;}

 inline int Min(int x,int y) {return x>y?y:x;}

 inline LL Max(LL x,LL y) {return x>y?x:y;}

 inline void Swap(int &x,int &y) {int t=x;x=y;y=t;}

 inline void Get_Int(int &x)

 {

     x=; register char ch=getchar(); int f=;

     while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

     while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();} x*=f;

 }

 int main()

 {

     Get_Int(n);

     for (int i=;i<=n;i++)

     {

         Get_Int(P[i].l),Get_Int(P[i].r),Get_Int(P[i].w);

         if (P[i].l>P[i].r) Swap(P[i].l,P[i].r);

         a[i*-]=P[i].l,a[i*]=P[i].r;

     }

     sort(a+,a+n*+); Cnt=;

     for (int i=;i<=*n;i++) if (a[i]!=a[Cnt]) a[++Cnt]=a[i];

     for (int i=;i<=n;i++) P[i].l=lower_bound(a+,a+Cnt+,P[i].l)-a,P[i].r=lower_bound(a+,a+Cnt+,P[i].r)-a;

     sort(P+,P+n+,Cmp); int j=;

     for (int i=;i<=Cnt;i++)

     {

         while (j<=n && P[j].r==i)

         {

             F[i]=Max(F[i],F[P[j].l]+(LL)P[j].w);

             j++;

         }

         F[i]=Max(F[i],F[i-]);

     }

     printf("%lld\n",F[Cnt]);

     return ;

 }

线段覆盖5

不会贪心只会DP，Code都类似只不过中间用STL离散化被卡常了..

04-13 21:36
Powered by LMLPHP ©2024 线段覆盖 0.071246