萌新求助dp

CF1009F Dominant Indices

UltiMadow @ 2020-07-05 12:12:42

我一开始dp是这么写的：

for(int j=1;j<=dep[v]+1;j++)
{
    f[u][j]+=f[v][j-1];
    if(f[u][ans[u]]<f[u][j]||(f[u][ans[u]]==f[u][j]&&j<ans[u]))
        ans[u]=j;
}

然后 WA#28

然后改成这样：

for(int j=1;j<=dep[v];j++)
{
    f[u][j]+=f[v][j-1];
    if(f[u][ans[u]]<f[u][j]||(f[u][ans[u]]==f[u][j]&&j<ans[u]))
        ans[u]=j;
}

就 A 了

问一下为啥啊，因为我现在还是觉得上面那个是对的（

因为上面那个转移到了 f[v][dep[v]] 而下面那个没有转移到

求解qwq

by UltiMadow @ 2020-07-05 12:20:38

@Flying_Bird 加了

by UltiMadow @ 2020-07-05 12:21:26

@耶耶小朋友都在上面剪切板里了（

by _5011_ @ 2020-07-05 12:22:07

@UltiMadow 可能是你分配的内存池溢出了？

by UltiMadow @ 2020-07-05 12:22:30

@Zephyr_ 哦有道理我再试试

by Semsue @ 2020-07-05 12:23:10

蒟蒻不会长链剖分，滚了滚了

by LCuter @ 2020-07-05 12:24:11

@UltiMadow 单独的一个点，它的 dep 是 1 ，所以 +1 的话会超出去吧？

by UltiMadow @ 2020-07-05 12:24:45

@Zephyr_ 是内存池分配小了qwq

第一种改成 f[v]=p;p+=dep[v]+1; 就没问题了

此贴完结

by _5011_ @ 2020-07-05 12:25:43

考古

by UltiMadow @ 2020-07-05 12:26:13

然后我懂了第二种为啥是对的了（（（

没必要转移f[v][dep[v]]

~~从 0 开始和从 1 开始傻傻分不清/youl~~

by CSP_Sept @ 2020-07-05 12:27:52

kaogu（