[treeDp][状态分析][dfs] UVa12093 Protecting Zonk

这个题确实是,自己想没有整出来。由于多考虑了一层,状态变得复杂了。

首先还是转化为有根树去做,然后考虑下自底向上的推法。因为这里多考虑一层,所以还需要考虑子节点的放置情况,也就是除了考虑i节点放A/放B/不放,还需要考虑i的子节点,有没有放B/放A/不放,这样的话可以发现所有的情况到最后可以归类为4类,1)i处放B 2)i处放A且子节点放A/放B/没但是其字节点全放A/B,或者i处不放,其字节点至少有一个放B 3)i处不放,但是子节点全为2状态 4)能保证父节点放一个B就能覆盖到往下所有未覆盖路径的任意状态。然后就可以把状态转移方程搞出来,记忆化搜索即可。

自己思考存在的问题:脱离了无后效性这个基本点在想。如果按照一遍dfs来dp的思路,应该是保证了子树推出来之后才能推更高的祖先。

wa的话,因为用了一个cur的变量,之后再用却没有正确赋值。。。

#include

using namespace std;
const int maxn=1e5+5;
const int mod=1e9+7;


vectorG[maxn];
int vis[maxn][4];
int n,c1,c2,u,v;

int d(int i,int s,int p)
{
    if(~vis[i][s])
        return vis[i][s];
    int ans=0;
    int len=G[i].size(),cur;

    for(int j=0;j
	

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

此站点使用 Akismet 来减少垃圾评论。了解我们如何处理您的评论数据