[洛谷P4395][题解][BOI2003]Gem 气垫车
0.咕
又水了一篇题解qwq
1.解法
12染色和123染色都是错的,我们考虑直接暴力\(dp\)。
设\(f[i][j]\)为\(i\)填\(j\)时\(i\)子树的最小值。
方程很简单:\(f[now][j]=\sum_{k\ne j} \min(f[son][k])\)。
氮素!这个方程是\(O(n^3)\)的!
怎么办?
我们发现有很多数是没必要填的,也就是转移的\(O(n^2)\)是不需要跑满的。
题解区有最大数\(\log n\)的证明,自己做的时候随便选一个能过的数就行了。
2.代码
#define N 10010
int n,f[N][20],ans=INF;
struct Edge {
int to,nxt;
}e[N<<1];
int head[N],cnt;
inline void ade(int u,int v){
e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
}
void DFS(int now,int ff){
for(rg int i=1;i<20;i++)f[now][i]=i;
for(rg int i=head[now];i;i=e[i].nxt){
int v=e[i].to;
if(v!=ff){
DFS(v,now);
for(rg int j=1;j<20;j++){
int res=INF;
for(rg int k=1;k<20;k++){
if(j!=k)res=min(res,f[v][k]);
}
f[now][j]+=res;
}
}
}
}
int main(){
Read(n);
for(rg int i=1;i
3.后记
按照\(\log n\)的大小把代码里的20改成14,一跃成为最优解……
有图为证(前两个都是改后代码区别只有\(O2\)):