Ryan_<

POJ1947 Rebuilding Roads

状态转移方程实际上是一个泛化背包模型

注意"空间"的枚举顺序.

void DFS(int u)
{
    for(int i = 0; i <= m; i++) //初始化为无穷大
        dp[u][i] = INF;               
    dp[u][1] = 0;               //根结点本就一个点，不需要减边
    for(int i = head[u]; i != -1; i = e[i].next)
    {
        int v = e[i].to;    //u的子树
        DFS(v);
        for(int j = m; j >= 1; j--) 
        {
            for(int k = 0; k < j; k++)
            {
                if(k)   //不加子树k
                    dp[u][j] = min(dp[u][j], dp[u][j - k] + dp[v][k]);//此时dp[u][j-k]与dp[v][k]均被计算过 
                else    //加上子树k
                    dp[u][j] = dp[u][j] + 1;
            }
        }
    }
}
/*****main*****/
    DFS(root);
    int ans = dp[root][m];
    for(int i = 1; i <= n; i++)     //除了根节点，其他节点要想成为独立的根，必先与父节点断绝关系，所以要先加1
        ans = min(ans, dp[i][m] + 1);

POJ2486 Apple Tree

做了上面的题,这道题状态就很好想了.

可是:在进行背包的时候，对于某个孩子,走完之后是否回到根结点会对后面是否还能分配有影响

那就多加一维状态,分类讨论

void dfs(int s){
    int i;
    used[s]=true;
    for(i=0;i<=V;i++){
         dp[0][s][i]=dp[1][s][i]=val[s];//强制加入
    }
    for(i=0;i<g[s].size();i++){
        int t=g[s][i];
        if(used[t]) continue;
        dfs(t);
        for(int j=V;j>=0;j--){
            for(int k=0;k<=j;k++){//中间的桥梁一定要走，所以把状态依次转变过来
                Max(dp[0][s][j+2],dp[0][t][k]+dp[0][s][j-k]);
                Max(dp[1][s][j+2],dp[0][t][k]+dp[1][s][j-k]);
                Max(dp[1][s][j+1],dp[1][t][k]+dp[0][s][j-k]);
            }
        }
    }
}
/*****main*****/
    memset(dp,0,sizeof(dp));
    memset(used,false,sizeof(used));
    dfs(1);
    printf("%d\n",dp[1][1][V]);

POJ3140 Contestants Division

题意概括和建模很重要,还要有常~~识~~

树形Dp个毛线啊

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
#define LL __int64
struct node{
    int v , next ;
}edge[210000] ;
int head[110000] , cnt , vis[210000];
LL c[110000] , min1 , ans ;
void add(int u,int v) {
    edge[cnt].v = v ; edge[cnt].next = head[u] ;
    head[u] = cnt++ ;
    edge[cnt].v = u ; edge[cnt].next = head[v] ;
    head[v] = cnt++ ;
    return ;
}
LL f(LL a) {
    return a >= 0 ? a : -a ;
}
void dfs(int u) {
    int i ;
    LL temp ;
    for(i = head[u] ; i != -1 ; i = edge[i].next) {
        if( vis[i] == 0 ) {
            vis[i] = vis[i^1] = 1 ;
            dfs(edge[i].v) ;
            temp = f(ans-c[edge[i].v]-c[ edge[i].v ]) ;
            if( temp < min1 ) min1 = temp ;
            c[u] += c[ edge[i].v ] ;
        }
    }
}
int main() {
    int n , m , t = 0 , i , j , u , v ;
    while( scanf("%d %d", &n, &m) != EOF ) {
        if( n == 0 && m == 0 ) break ;
        memset(head,-1,sizeof(head)) ;
        memset(vis,0,sizeof(vis)) ;
        cnt = 0 ;
        ans = 0 ;
        for(i = 1 ; i <= n ; i++) {
            scanf("%I64d", &c[i]) ;
            ans += c[i] ;
        }
        min1 = ans ;
        while( m-- ) {
            scanf("%d %d", &u, &v) ;
            add(u,v) ;
        }
        dfs(1) ;
        printf("Case %d: %I64d\n", ++t, min1) ;
    }
    return 0 ;
}

POJ2057 The Lost House

截(sang)图(xin)留(bing)念(kuang)

LA2038 战略游戏