首页 > 代码库 > topcoder srm 662 div1 -3
topcoder srm 662 div1 -3
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]; }};
topcoder srm 662 div1 -3
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。