传送门
题目大意：
一个 \(n\) 个叶子节点，一个节点最多可以有 \(k\) 条边连向子节点，每个节点 \(i\) 有一个权值 \(P_{i}\)。记每个节点子树内点的个数（不包括它自己）为 \(son_{i}\)，那么每个节点对答案的贡献就是 \(son_{i}^2 \times P_{i}\)。特别的，根节点贡献为 \(0\)，求总贡献。
两种解法：记忆化搜索和 DP，两种解法本质一样只是写法不同。
一、记忆化搜索：
首先贪心的对点权 \(P_{i}\) 升序排序。
设 \(dp_{rest,now}\) 表示还剩 \(rest\) 个节点要连，当前考虑的是第 \(now\) 个指针的总贡献。
分三种情况转移：
- 只剩一个节点，直接连上走人，加上当前点的贡献：\(dp_{rest,now}=val_{now}\)。
- 只剩一个指针并且剩下的节点不止一个，开下一层，并加上当前点的贡献：\(dp_{rest,now}=dp_{rest,1}+val_{now}\times rest\times rest\)。
- 以上两种情况都不满足，将这个指针作为目录，枚举其连接的点数进行转移：\(dp_{rest,now}=\min_{i\in[2,rest)}{dp_{rest,now},dp_{rest-i,now+1}+dp_{i,1}+val_{now}\times i\times i}\)。
\(\mathcal{Code}\)：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define il inline
#define re register
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define F(i,a,b) for(re int (i)=(a);(i)<=(b);(i)++)
#define DF(i,a,b) for(re int (i)=(a);(i)>=(b);(i)--)
#define G(i,u) for(re int (i)=head[u];(i);(i)=nxt[(i)])
inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}return x*f;}
const int N=1010,K=160;
int n,k;
int val[K];
int dp[N][K];
il int dfs(int rest,int now)//剩rest个点要连，当前用这一层的第now个指针
{
if(dp[rest][now]!=INF) return dp[rest][now];//记忆化
if(rest==1)//只剩一个节点，直接连上走人
return dp[rest][now]=val[now];
if(now==k)//只剩一个指针并且连不完，再开一层
return dp[rest][now]=dfs(rest,1)+val[now]*rest*rest;//val[now]*rest*rest是当前指针对答案的贡献
dp[rest][now]=min(dp[rest][now],dfs(rest-1,now+1)+val[now]);//就这个指针作为叶子节点的情况
F(i,2,rest-1)//这个指针作为目录，连i个点的情况
dp[rest][now]=min(dp[rest][now],dfs(rest-i,now+1)+dfs(i,1)+val[now]*i*i);//val[now]*i*i是当前指针对答案的贡献
return dp[rest][now];
}
int main()
{
memset(dp,0x3f,sizeof(dp));
n=read(),k=read();
F(i,1,k) val[i]=read();
sort(val+1,val+k+1);
printf("%d",dfs(n,1));
return 0;
}
二、DP：
还是先贪心的对点权 \(P_{i}\) 升序排序。
TIP：为了防止变量重名，将原先的指针数量 \(k\) 改成了 \(m\)。
设 \(dp_{i,j}\) 表示在当前目录下，用前 \(j\) 个指针放 \(i\) 个文件，所增加的贡献。
设 \(g_{i}\) 表示放 \(i\) 个文件的最少时间，\(g_{n}\) 即所求答案。
先预处理 \(dp_{1,i}=val_{i}(i\in[1,k])\) 表示只放一个文件的特殊情况，这种情况不用开目录直接放。
还要预处理 \(g_{1}=0\)，这是因为只放一个文件是不用开目录的，在转移时会统计目录的贡献，由于只放一个点时开目录贡献和叶子节点的贡献一样，为了防止重复，将 \(g_{1}\) 设为 \(0\)，并对 \(n=1\) 的情况特判。
这里有个小剪枝：要使答案最优，数值大的指针放的文件个数一定小于等于数值小的指针放的文件个数，均摊的情况即 \(\lfloor \frac{i}{j} \rfloor\)，将此作为上界以减少转移次数。
转移时枚举之前的指针目录下已经放置的文件 \(k\)，对当前的 \(dp_{i,j}\) 进行更新，转移即：\(dp_{i,j}=\min_{k\in[1,i-j+1]}{dp_{i,j},dp_{i-k,j-1}+g_{k}+k\times k\times val_{j}}\)。
然后对 \(g_{i}\) 和特殊情况 \(dp_{i,1}\) 进行更新用于下一轮的转移。
\(\mathcal{Code}\)：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define il inline
#define re register
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define F(i,a,b) for(re int (i)=(a);(i)<=(b);(i)++)
#define DF(i,a,b) for(re int (i)=(a);(i)>=(b);(i)--)
#define G(i,u) for(re int (i)=head[u];(i);(i)=nxt[(i)])
inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}return x*f;}
const int N=1010,K=160;
int n,m;
int val[K];
int dp[N][K],g[N];//dp[i][j]表示放i个文件，用了前j个指针所花；g[i]表示放i个文件的最优解
int main()//贡献记为：子文件个数×当前指针的值
{
memset(dp,0x3f,sizeof(dp));
memset(g,0x3f,sizeof(g));
n=read(),m=read();
F(i,1,m) val[i]=read();
sort(val+1,val+m+1);
if(n==1) return printf("%d",val[1]);//因为g[1]设为了0，所以n=1时要特判
g[1]=0;//只放一个文件，不用开目录，这个文件自身的贡献在转移时已被计算，所以这里的贡献设为0
F(i,1,m) dp[1][i]=val[i];//第i个指针，放1个文件，直接放，贡献为val[i]
F(i,2,n)
{
F(j,2,min(i,m))
F(k,1,i/j)//剪枝：贪心的想：大指针放的文件个数一定小于等于小指针放的文件个数，所以设定上界i/j即均摊的情况
dp[i][j]=min(dp[i][j],dp[i-k][j-1]+g[k]+k*k*val[j]);
F(j,2,min(i,m))//更新最优解
g[i]=min(g[i],dp[i][j]);
dp[i][1]=g[i]+i*i*val[1];//更新只用一个指针的情况用于更新
}
printf("%d",g[n]);
return 0;
}