2016.7.16DP考试总结

今日试题

今天我虐场了~~~然而只有20分,今天的题目简直是难炸了,出题人自信说送了300分,然而一个30分都没有……二十分就虐场了,相当高兴。事实上今天的动规练习赛已经彻底变成暴力练习赛了……看完题目我都是两眼一抹黑的……第一题有点想法,想了半天无果,放弃,第四题写了个DP+贪心,WA……已经没有什么好害怕的了……

1、rebuilt

看到题目,马上就懂了,然后将题目的条件整合了一下,发现是一棵基环外向树上面选不相交的权值和最大的边。然后我没有想到可以找环删边变成树形DP,于是只能写暴力。

%%%出题人TMJ大爷

%%%WA+MLE的YJP大爷

%%%WA的XYK大爷

你们好歹想出正解了,我果然还是个蒟蒻。

正解:对于每个独立的基环外向树,首先处理不在环上的链,然后对于每一个环选择一条边,强制其选或不选,然后树形DP得出最优答案。

2、chase

这题我一脸懵逼,完全不会做。。。暴力都写不出。事实上这题第一问是BZOJ3622已经没有什么好害怕的了,第一问不会做,第二问听了讲题后会做了,感觉很有道理,这里就不给正解了,慢慢补上。

3、diplomacy

完全是被题面吓到了的说。事实上很简单,只要做很多遍单调队列然后更新答案就行了。

定义f[i]为第i天买入股票后所持金额,g[i]为第i天卖出股票后所持金额。

f[i]=g[j]-x1[i].(j-b2<=i<=j-b1)

g[i]=f[j]+x2[i]+pr*(j-i);(j-a2<=i<=j-a1)

然后就可做了。。。用个单调队列+滑动窗口即可。

加上我抽象画风,单调队列是这种东西:

无标题

4、evocation

这题一看到就写了个贪心,然后小数据都WA了……QAQ,我真傻真的,事实上暴力有15分(不过好像没什么人拿到的样子)这道题是讲过的原题,然而讲的时候没怎么听懂,现在大概懂了一点,然而g函数到底怎么构造还是不知道,翻论文吧www

我已经醉了

朴素思维f[i][k][w],表示在子树i中建造k个祭坛,尚有w英灵未经处理,但无论是空间还是时间都不能接受。于是考虑优化算法。定义f[now][fa][k],表示当前节点为now,最近父亲祭坛为fa,选择k个时最小总路程。每个节点有选与不选两种选择,选则进入g(son,now,k-1),否则进入g(son,fa,k-1)。但是要从叶子往上推(逆BFS序),保证每个只计算一次。边界情况g(leaf,fa,0)=deep[leaf]。

DP果然我是蒟蒻……没有一道题是会做的。。。

再刷100题再说吧,就这样了。。。

不如来评论一发?