[BZOJ4899] 记忆的轮廓
其实是一个比较明显的分段型决策单调性优化
\(dp[i][j]\) 表示前 \(i\) 个主节点, 分了 \(j\) 段的答案
单调性: 段数越多, 决策点越靠近 \(i\), 对于每一个 \(i\) 分治每一个 \(j\) 即可
转移比较麻烦, 要解一个方程, 记录一下系数, 预处理出来每一棵子树的系数和, 然后累出一段区间的和计算贡献
注意最优方案的期望题倒着 \(dp\) 是常规操作
- const int N=710,M=1510;
- const double INF=1e18;
- bool be;
- int n,m,p;
- struct Edge{
- int to,nxt;
- }e[M];
- int head[M],ecnt;
- void AddEdge(int u,int v){
- e[++ecnt]=(Edge){v,head[u]};
- head[u]=ecnt;
- }
- #define erep(u,i) for(int i=head[u];i;i=e[i].nxt)
- double dx[N][N],dy[N][N];
- double sx[M],sy[M];
- double dp[N][N];
- int son[M];
- void dfs(int u) {
- son[u]=0;
- sx[u]=sy[u]=0;
- erep(u,i) {
- int v=e[i].to;
- son[u]++;
- dfs(v);
- sx[u]+=sx[v];
- sy[u]+=sy[v];
- }
- if(u<=n) son[u]++;
- if(son[u]) sx[u]/=son[u],sy[u]/=son[u];
- else sx[u]=1;
- sy[u]++;
- }
- void Pre_Make(){
- rep(i,1,n-1) dfs(i); // 预处理子树内的系数和
- rep(i,2,n) {
- double t=1,x=0,y=0;
- drep(j,i-1,1) {
- t/=son[j],x/=son[j],y/=son[j];
- x+=sx[j],y+=sy[j];
- dx[j][i]=t/(1-x);
- dy[j][i]=y/(1-x); // 解方程, t 存下 dp[i] 的系数
- }
- }
- }
- void Solve(int p,int l,int r,int L,int R) {
- if(l>r) return;
- int mid=(l+r)>>1;
- double mi=INF,id=L;
- rep(i,L,R) if(dp[i][mid-1]<INF) {
- double t=dx[p][i]*dp[i][mid-1]+dy[p][i];
- if(t<mi) mi=t,id=i;
- }
- dp[p][mid]=mi;
- Solve(p,l,mid-1,id,R);
- Solve(p,mid+1,r,L,id);
- }
- int main(){
- rep(kase,1,rd()) {
- n=rd(),m=rd(),p=rd();
- memset(head,0,sizeof head); ecnt=0;
- rep(i,1,m-n) {
- int u=rd(),v=rd();
- AddEdge(u,v);
- }
- Pre_Make();
- rep(i,1,n) rep(j,0,p) dp[i][j]=INF;
- rep(i,1,p) dp[n][i]=0;
- drep(i,n-1,1) Solve(i,2,p,i+1,n);
- printf("%.4lf\n",dp[1][p]);
- }
- }
来源: http://www.bubuko.com/infodetail-3258432.html