【AHOI2013复仇】NOI2008 道路设计

Posted on 2012-09-22 16:21 Mato_No1 阅读(699) 评论(0)  编辑 收藏 引用 所属分类: NOI动态规划
原题地址
典型的二次递推/DP的题目。
首先,题目中的“不便利值”指的是某个点到根的路径上的木有被选定链覆盖的边的条数。

第一问:设F[i][0..2]分别为当子树i中结点i的状态为不参与链(0)、作为某链端点(1)、作为某链中间点(2)时,子树i中的结点到i的最小不便利值。为了得到F,需要设立G[j][k(0..2)]表示结点i的前j棵子树中,有k棵的根结点与结点i接上的最小的最大不便利值。显然,不和i接上的,状态为0、1、2都行,但不便利值要加1,而和i接上的状态只能是0或1,不加1。

问题是第二问。第二问的难点在于,当i取得最小不便利值时,i的每个子结点并非都取到最小不便利值。举个例子,结点i的最小不便利值为3,它的某个子结点j的最小不便利值为2,则当j与i接上时,子树j的内部既可以取不便利值为2的解,也可以取不便利值为3的解。所以,为了解决第二问,需要求出结点i的最小不便利值为x的解的总数。万幸的是,x的范围并不是太大,可以证明,x不会超过log3N(下取整),也就是当N=100000时x最大为10。因此,最后仍然不会T掉。

这题的一个启示就是,在求类似于“最优解计数”的问题中,不要认为当后面的状态取得最优解时,前面的状态一定取得最优解。因此,不能只记录某状态取得最优解的个数,而要记录该状态取得每一个可行解时的个数。

代码:
#include <iostream>
#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 100010, MAXW = 11, INF = ~0U >> 2;
struct edge {
    
int a, b, pre, next;
} E0[MAXN 
* 3], E[MAXN << 1];
int n, m0, m, Q[MAXN], F[MAXN][3], G[MAXN][3], res1 = 0;
ll MOD, FS[MAXN][MAXW][
3], S[MAXN][MAXW][3], res2 = 0;
bool vst[MAXN];
void init_d()
{
    re(i, n) E0[i].pre 
= E0[i].next = E[i].pre = E[i].next = i; m0 = m = n;
}
void add_edge0(int a, int b)
{
    E0[m0].a 
= a; E0[m0].b = b; E0[m0].pre = E0[a].pre; E0[m0].next = a; E0[a].pre = m0; E0[E0[m0].pre].next = m0++;
    E0[m0].a 
= b; E0[m0].b = a; E0[m0].pre = E0[b].pre; E0[m0].next = b; E0[b].pre = m0; E0[E0[m0].pre].next = m0++;
}
void add_edge(int a, int b)
{
    E[m].a 
= a; E[m].b = b; E[m].pre = E[a].pre; E[m].next = a; E[a].pre = m; E[E[m].pre].next = m++;
}
void init()
{
    
int _M; scanf("%d%d"&n, &_M); cin >> MOD; if (_M < n - 1) {res1 = res2 = -1return;} init_d(); int a0, b0;
    re2(i, 
1, n) {scanf("%d%d"&a0, &b0); add_edge0(--a0, --b0);}
}
void prepare()
{
    re(i, n) vst[i] 
= 0; Q[0= 0; vst[0= 1int x, y;
    
for (int front=0, rear=0; front<=rear; front++) {
        x 
= Q[front];
        
for (int p=E0[x].next; p != x; p=E0[p].next) {
            y 
= E0[p].b;
            
if (!vst[y]) {vst[y] = 1; Q[++rear] = y; add_edge(x, y);}
        }
    }
    re(i, n) 
if (!vst[i]) {res1 = -1; res2 = -1return;}
}
inline 
int minv3(int s1, int s2, int s3)
{
    
int s0 = s1 <= s2 ? s1 : s2;
    
return s0 <= s3 ? s0 : s3;
}
inline 
int minv2(int s1, int s2)
{
    
return s1 <= s2 ? s1 : s2;
}
void solve()
{
    
int x, y, len, v1, v2, v01, v02; ll sum;
    rre(i, n) {
        x 
= Q[i]; len = 0; G[0][0= 0; G[0][1= G[0][2= INF;
        
for (int p=E[x].next; p != x; p=E[p].next) {
            y 
= E[p].b; len++;
            v1 
= minv3(F[y][0], F[y][1], F[y][2]) + 1; v2 = minv2(F[y][0], F[y][1]);
            G[len][
0= v1 >= G[len - 1][0? v1 : G[len - 1][0];
            v01 
= v1 >= G[len - 1][1? v1 : G[len - 1][1];
            v02 
= v2 >= G[len - 1][0? v2 : G[len - 1][0];
            G[len][
1= minv2(v01, v02);
            v01 
= v1 >= G[len - 1][2? v1 : G[len - 1][2];
            v02 
= v2 >= G[len - 1][1? v2 : G[len - 1][1];
            G[len][
2= minv2(v01, v02);
        }
        re(j, 
3) F[x][j] = G[len][j];
        re(j, MAXW) {S[
0][j][0= 1; S[0][j][1= S[0][j][2= 0;} len = 0;
        
for (int p=E[x].next; p != x; p=E[p].next) {
            y 
= E[p].b; len++;
            re(j, MAXW) re(k, 
3) {
                S[len][j][k] 
= 0;
                
if (j) {
                    sum 
= 0; re(k0, 3) {sum += FS[y][j - 1][k0]; if (sum >= MOD) sum -= MOD;}
                    S[len][j][k] 
= (sum * S[len - 1][j][k]) % MOD;
                }
                
if (k) {
                    sum 
= 0; re(k0, 2) {sum += FS[y][j][k0]; if (sum >= MOD) sum -= MOD;}
                    S[len][j][k] 
= (S[len][j][k] + sum * S[len - 1][j][k - 1]) % MOD;
                }
            }
        }
        re(j, MAXW) re(k, 
3) FS[x][j][k] = S[len][j][k];
    }
    res1 
= minv3(F[0][0], F[0][1], F[0][2]);
    res2 
= 0; re(i, 3if (F[0][i] == res1) res2 += FS[0][F[0][i]][i]; res2 %= MOD;
}
void pri()
{
    cout 
<< res1 << endl << res2 << endl;
}
int main()
{
    init();
    
if (!res1) prepare();
    
if (!res1) solve();
    pri();
    
return 0;
}



只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理