第一场-H - Highest Tower

题目链接：点击打开链接

（一）题目大意：

  给出n个已知长和宽的矩形，当矩形A的某一条边长度严格小于矩形B的一边长度时，矩形A可以放在矩形B的上方，两个矩形接触的一边作为宽，另外一边作为高，问将n个矩形全部摞起来的高度最高为多少。比如有三个矩形：（5，10），（5，10），（5，16）。那么这三个矩形可以以下面的方式堆，得到的高度为20：

（二）解题思路：

1. 对于两个矩形而言，如果两个矩形的边长没有相等的，那么这两个矩形可以得到的最高的高度就是两个矩形的长边之和。由此可以容易地归纳得到：若两堆矩形（堆内可能有相等地边）之间没有相等地边，那么这两堆矩形可以得到地最优解就是各自最优解地和。那么我们接下来就只考虑求存在相等的边地一个矩形集合的最优解，因为最终的最优解就是这些最优解的和。
2. 由于只有当边长严格递减时，两个矩形才能堆起来，那么就不可能出现相等得宽，即：若一个矩形集合中值为V的边长出现了K次，那么这K次中最多只能有一次作为宽边，其它全部得作为高，而一旦确定了一条边为高，那么相当于就确定了一个矩形的摆的方式。
3. 我们先把所有同一个集合的矩形“连”起来：以边长的值作为顶点（这里边长太大，需要离散化），同一个矩形的两个边长之间建边，举个栗子：
4. 我们根据建的图的各个点的度，即可以判断出该节点会至少作为几次高出现，也就知道了确定了摆放方式的矩形个数，下面做一个定量的分析。
5. 设图中有n个顶点，m条边（m个矩形），那么就总共有2m个度，除去每个顶点的一个度，还剩2m-n个，也就是作为高的边的数目，也就是确定的矩形的数目。
6. 当m==n时：2m-n==n(被确定的矩形数目)，n-n==0，即所有的矩形都已经被确定，我们在遍历节点的时候直接把所有作为高的边的长度求和就是结果。
7. 当m==n-1时：2m-n==n-2（被确定的矩形数目），n-1-(n-2)==1，即存在1个不确定摆放方式的矩形，基于贪心的思想，我们直接取最长的边作为高即可得到最优解。
8. m<n-1：图不连通。m>n：无解。
9. 综上：对于一个矩形的集合，我们先把确定作为高的边长求和，再根据边和点的关系来决定是否需要加上最长边。不同集合之间直接求和得到最终结果

（三）具体代码：

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn=2e6+10;
map<int,int>mp;
vector<int>G[maxn];
int vis[maxn],val[maxn];
LL ans=0;
int _max=-1,node=0,edge=0;
void DFS(int u){
    _max=max(_max,val[u]);
    int sz=G[u].size();
    if(sz>=2)ans+=(LL)(sz-1)*(LL)val[u];
    node++;edge+=sz;vis[u]=1;
    for(int i=0;i<sz;i++){
        int v=G[u][i];
        if(!vis[v]){vis[v]=1;DFS(v);}
    }
}
int main(){
    freopen("in.txt","r",stdin);
    int n,x,y,u,v,cnt=1;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&u,&v);
        if(!mp[u])mp[u]=cnt++;
        if(!mp[v])mp[v]=cnt++;
        x=mp[u],y=mp[v];
        G[x].push_back(y);
        G[y].push_back(x);
        val[x]=u;val[y]=v;
    }
    for(int i=1;i<cnt;i++){
        _max=-1,node=0,edge=0;
        if(!vis[i]){
            DFS(i);edge>>=1;
            if(node==edge+1)ans+=_max;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

看到这个题以后就感觉是DP，然后让队友去怼23333，结果可想而知...看到题解后才惊了。