CSAcademy 是一个比较小众的罗马尼亚OJ，UI好看功能多样，但是需要fq才能注册。访问是不用fq的
前段时间刚做过类似的分层dp题，这次又忘了，深刻反思.jpg
题目要求构造一棵n个叶子的二叉树，发现一定存在一个最优解，满足构造出的树每个非叶节点都有两个儿子，因为空着一个儿子不用一定是不优的。如果树已经构造出来了，我们就把所有叶子按到根节点的距离排序，然后频率最高的字符占距离最小的节点，然后频率最低的字符占距离最大的节点，以此类推，这样显然是坠吼的~ 乍一看只能想到指数级的状压做法，很寄。但是由于每个节点都有两个儿子，一个到它距离为1，另一个距离为2，我们不妨把这棵树分层：
令根节点在第0层，其左儿子在第1层，右儿子在第2层…… 然后设置dp状态，\(dp_{i,j,k,p}\)表示已经到了第i层，第i-1层有j个非叶节点，第i层有k个非叶节点，现在需要放在第i层及之前的字母已经全部放置完毕，一共放了p个字母(频率最高的p个)；接下来要进行的是放置第i+1层的节点，以及在第i+1层选一些点作为叶子。上面说了非叶节点只有1个儿子是不优的，所以把这种情况统计进去也不影响答案。转移时枚举第i+1行放r个字母，转移到\(dp_{i+1,k,min(n,j+k-r),p+r}\)。其中\(min(n,j+k-r)\)是因为下一层的节点肯定越多越好，但是超过n个就没用了。直接这么写的复杂度是\(O(n^5)\)。
发现i这一维是没用的，去掉也可以正常转移。转移过程中要么p增长，要么k不减少，所以不会产生环，只要先枚举p、再枚举k、最后枚举j就行了。时间复杂度变成\(O(n^4)\)。
进一步发现转移的时候不必枚举r，可以先由\(dp_{j,k,p}\)转移到\(dp_{k,min(n,j+k),p}\)，然后再额外加一步转移\(dp_{j,k,p} \to dp_{j,k-1,p+1}\)就行了，实现了化整为零，把大段的转移分成一步步走。
时间复杂度\(O(n^3)\)。
点击查看代码
include <bits/stdc++.h>
define rep(i,n) for(int i=0;i<n;++i)
define repn(i,n) for(int i=1;i<=n;++i)
define LL long long
define pii pair <int,int>
define fi first
define se second
define mpr make_pair
define pb push_back
void fileio()
{
ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
endif
}
void termin()
{
ifdef LGS
std::cout<<"\n\nPROGRAM TERMINATED";
endif
exit(0);
}
using namespace std;
const LL inf=1e18;
void chmin(LL &x,LL y){if(x>y) x=y;}
LL n,a[760],dp[2][760][760],rsum[760];
int main()
{
fileio();
//freopen("desire.in","r",stdin);
//freopen("desire.out","w",stdout);
cin>>n;
rep(i,n) cin>>a[i];
sort(a,a+n);reverse(a,a+n);
for(int i=n-1;i>=0;--i) rsum[i]=rsum[i+1]+a[i];
rep(i,2) rep(j,n+3) rep(k,n+3) dp[i][j][k]=inf;
dp[0][1][1]=rsum[0];
rep(ii,n)
{
int i=ii&1;
rep(k,n+1) rep(j,n+1) if(dp[i][j][k]<inf)
{
//cout<<ii<<' '<<j<<' '<<k<<' '<<dp[i][j][k]<<endl;
if(k>0) chmin(dp[i^1][j][k-1],dp[i][j][k]);
chmin(dp[i][k][min((LL)j+k,n)],dp[i][j][k]+rsum[ii]);
dp[i][j][k]=inf;
}
}
LL ans=inf;
rep(i,n+1) rep(j,n+1) chmin(ans,dp[n&1][i][j]);
cout<<ans<<endl;
termin();
}
这份代码在CSA老爷机上是会被卡常的，但是我本地可以轻松过。
标签：rsum,题解,rep,Telegraph,Academy,LL,节点,dp,define From： https://www.cnblogs.com/legendstane/p/CS-Academy-telegraph-solution-level-separate-dp.html