SDOI2006 보안근무

전송문
아주 좋은 나무 DP
처음에 나의 상태 선택은 dp[i][0]로 i를 뿌리 노드로 하고 i의 최소 비용을 선택하지 않았다. dp[i][1]은 i를 뿌리 노드로 하고 i의 최소 비용을 선택했다.그러나 이렇게 해서 나는 옮길 수 없다는 것을 발견했다. 왜냐하면 너는 선택하거나 선택하지 않는 정확성을 보장할 수 없기 때문이다.
문제는 컨디션 설정이 적다는 점이다.하나는 세 가지 상황이 있는데 하나는 자체 경비원이 있는 것이고 하나는 자신의 하위 노드에 의해 통제되고 하나는 통제되지 않는 것이다(장래는 아버지에 의해 통제될 것이다).우리는 dp[i][0]로 통제되지 않았다는 것을 나타내고 dp[i][1]는 자신의 아들 노드에 의해 통제되었다는 것을 나타내며 dp[i][2]는 자체적으로 보안이 되어 있다는 것을 나타낸다.
이후에 이동하면 쉽게 할 수 있다. dp[i][0] = ∑min(dp[v][1], dp[v][2])(v는 i의 서브노드인데 우리는 이 점을 만족시키는 서브노드만 모두 통제하면 되기 때문에 dp[i](dp[v][v][1], dp[v][2]))))(v는 [v][2])))(v는 i의 서브노드이고 우리가 이 점을 만족시키기만 하면 되기 때문에 우리는 이 점의 서브노드를 모두 통제하면 된다. dp[i]=∑min(dp[v][v][v][1][2], dp[v][v][v][v]]]][2]]]]]]], dp[v][v]][2]]]]]]]]], dp[v][2]]]]]노드 제어),강제로 선택하면 양자차의 최소값을 기록하고 선택이 없으면 최소값을 추가하면 된다.마지막으로 dp[i][2]는 이 노드 자체의 비용을 더해야 한다.
이제 유쾌한 DP가 될 거예요. 코드를 보세요.

#include
#include
#include
#include
#include
#include<set>
#include
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
#define enter putchar('
')

using namespace std;
typedef long long ll;
const int M = 10005;
const int INF = 1000000009;

int read()
{
    int ans = 0,op = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
    if(ch == '-') op = -1;
    ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
    ans *= 10;
    ans += ch - '0';
    ch = getchar();
    }
    return ans * op;
}

struct edge
{
    int next,to;
}e[M<<1];

int head[M],ecnt,w[M],dp[M][3],n,m,x,y;

void add(int x,int y)
{
    e[++ecnt].to = y;
    e[ecnt].next = head[x];
    head[x] = ecnt;
}

void dfs(int x,int fa)
{
    bool flag = 0;
    int minn = INF;
    for(int i = head[x];i;i = e[i].next)
    {
    int v = e[i].to;
    if(v == fa) continue;
    dfs(v,x);
    dp[x][2] += min(dp[v][0],min(dp[v][1],dp[v][2]));
    dp[x][0] += min(dp[v][1],dp[v][2]);
    if(dp[v][1] > dp[v][2]) dp[x][1] += dp[v][2],flag = 1;
    else dp[x][1] += dp[v][1],minn = min(minn,dp[v][2] - dp[v][1]);
    }
    dp[x][2] += w[x];
    if(!flag) dp[x][1] += minn;
}

int main()
{
    n = read();
    rep(i,1,n)
    {
    x = read(),w[x] = read(),m = read();
    rep(i,1,m) y = read(),add(x,y),add(y,x);
    if(!m) dp[x][1] = INF;
    }
    dfs(1,0);
    printf("%d
",min(dp[1][1],dp[1][2]));
    return 0;
}

 
전재 대상:https://www.cnblogs.com/captain1/p/9814331.html