topcoder srm 662 div1 -3

骑猪看日落 2021-05-02 12:19 207阅读 0赞

1、给出$n$个数字将其排列成一个环，使得相邻两个数字差的最大值最小。

思路：首先排序。然后从最小的数字开始，依次枚举将下一个数字放在左侧或者右侧。令$f\[i\]\[j\]\[k\]$表示已经放置了$i$个数字，其中左侧的最大数字编号是$j$，右侧最大数字编号是$k$的最小差值。

#include <stdio.h>
    #include <string.h>
    #include <string>
    #include <iostream>
    #include <vector>
    #include <set>
    #include <map>
    #include <queue>
    #include <algorithm>
    #include <stack>
    #include <assert.h>
    using namespace std;
    
    const int N=55;
    
    int f[N][N][N];
    int p[N][N][N][3];
    
    void up(int x,int y,int z,int X,int Y,int Z,int k) {
        if(p[x][y][z][0]==-1||max(k,f[X][Y][Z])<f[x][y][z]) {
            f[x][y][z]=max(k,f[X][Y][Z]);
            p[x][y][z][0]=X;
            p[x][y][z][1]=Y;
            p[x][y][z][2]=Z;
        }
    }
    
    class FoxesOfTheRoundTable
    {
    public:
        vector<int> minimalDifference(vector<int> h)
        {
            vector<pair<int,int>> a;
            const int n=(int)h.size();
            for(int i=0;i<n;++i) {
                a.push_back(make_pair(h[i],i));
            }
            sort(a.begin(),a.end());
    
            memset(p,-1,sizeof(p));
            f[0][0][0]=0;
            p[0][0][0][0]=0;
            for(int i=1;i<n;++i) {
                for(int x=0;x<i;++x) {
                    for(int y=0;y<i;++y) {
                        if(p[i-1][x][y][0]!=-1) {
                            up(i,i,y,i-1,x,y,a[i].first-a[x].first);
                            up(i,x,i,i-1,x,y,a[i].first-a[y].first);
                        }
                    }
                }
            }
    
            int ex=n-1,ey=0,ez=0;
            int ans=2222;
            for(int i=0;i<n;++i) {
                if(p[n-1][n-1][i][0]!=-1&&max(f[n-1][n-1][i],a[n-1].first-a[i].first)<ans) {
                    ans=max(f[n-1][n-1][i],a[n-1].first-a[i].first);
                    ey=n-1;
                    ez=i;
                }
                if(p[n-1][i][n-1][0]!=-1&&max(f[n-1][i][n-1],a[n-1].first-a[i].first)<ans) {
                    ans=max(f[n-1][i][n-1],a[n-1].first-a[i].first);
                    ey=i;
                    ez=n-1;
                }
            }
            vector<int> ll,rr;
            while(ex||ey||ez) {
                if(ey>ez) {
                    ll.push_back(ey);
                }
                else {
                    rr.push_back(ez);
                }
    
                int tx=p[ex][ey][ez][0];
                int ty=p[ex][ey][ez][1];
                int tz=p[ex][ey][ez][2];
                ex=tx;
                ey=ty;
                ez=tz;
            }
            ll.push_back(0);
            vector<int> result;
            for(int i=0;i<(int)ll.size();++i) result.push_back(a[ll[i]].second);
            for(int i=(int)rr.size()-1;i>=0;--i) result.push_back(a[rr[i]].second);
            return result;
        }
    };

2、对于一棵$n$个节点的树$T$来说，定义$d(i,j)$表示两个节点$i,j$之间的距离。定义$S(T)=\\sum\_\{0\\leq i<j<n\}d(i,j)$.给出$n,m,k$，构造一棵树$T$在满足使得$S(T)$%$m=k$的条件下使得$S(T)$最小？

思路：令$f\[n\]\[t\]$表示$n$个节点构成的树$T$满足$S(T)$%$m=t$的最小的$S(T)$。合并两棵树时有转移方程:$f\[n\]\[r\]=f\[x\]\[t0\]+f\[n-x\]\[t1\]+x\*(n-x)$，其中$r=(f\[x\]\[t0\]+f\[n-x\]\[t1\]+x\*(n-x))$%$m$。

#include <stdio.h>
    #include <string.h>
    #include <string>
    #include <iostream>
    #include <vector>
    #include <set>
    #include <map>
    #include <queue>
    #include <algorithm>
    #include <stack>
    #include <assert.h>
    using namespace std;
    
    
    int f[55][111];
    
    class ExactTree
    {
    public:
        int getTree(int n,int m,int r)
        {
            memset(f,-1,sizeof(f));
            f[1][0]=0;
            for(int i=2;i<=n;++i) {
                for(int x=1;x<i;++x) {
                    for(int t0=0;t0<m;++t0) for(int t1=0;t1<m;++t1) {
                        if(f[x][t0]!=-1&&f[i-x][t1]!=-1) {
                            int r=(f[x][t0]+f[i-x][t1]+x*(n-x))%m;
                            int s=f[x][t0]+f[i-x][t1]+x*(n-x);
                            if(f[i][r]==-1||s<f[i][r]) {
                                f[i][r]=s;
                            }
                        }
                    }
                }
            }
            return f[n][r];
        }
    };