POJ 1155 TELE [트리 DP]

제목: 생략.
사고방식: dp[i][k]로 결점 i가 k개 사용자에게 프로그램을 제공할 때의 최대 이익(마이너스일 수 있음)을 나타낸다.
점차적인 방정식은 dp[i][j]=max(dp[i][j], dp[i][m]+dp[v][j-m]-cost)이다.
그 중에서 v는 i의 아이이고,cost는 i가 v에게 프로그램을 제공하는 비용이다.
또한 코드에서 dp 과정의 이 몇 줄을 주의해라

1         for (int j = num[x]; j >= 0; j--)

2             for (int k = 1; k <= num[v]; k++)

3                 dp[x][j+k] = max(dp[x][j+k], dp[x][j] + dp[v][k] - edge[i].w);

현재 고려하고 있는 아이의 결점이 v라고 가정하면 아이 1...(v-1) 덮어쓰는 사용자 수는num[x]이며, i가 이미 고려한 사용자 수입니다.여기서 매거할 때 큰 것에서 작은 것까지 매거해야 한다. 그렇지 않으면 j=1의 상황이 j=2의 상황에 영향을 줄 수 있다.또 다른 처리 방법은 결점 i의 모든 dp[i][j]값을 매번tem[j]로 저장하고 dp일 때tem[j]를 직접 사용하면 매거진의 순서를 고려할 필요가 없다는 것이다.

 1 #include<stdio.h>

 2 #include<string.h>

 3 #include<algorithm>

 4 #define maxn 3005

 5 #define inf 0x3f3f3f3f

 6 using namespace std;

 7 struct node

 8 {

 9     int v, w, next;

10 }edge[maxn];

11 int num_edge, head[maxn];

12 void init_edge()

13 {

14     num_edge = 0;

15     memset(head, -1, sizeof(head));

16 }

17 void addedge(int a,int b,int c)

18 {

19     edge[num_edge].v = b;

20     edge[num_edge].w = c;

21     edge[num_edge].next = head[a];

22     head[a] = num_edge++;

23 }

24 

25 int n, m, num[maxn], dp[maxn][maxn];

26 void dfs(int x)

27 {

28     for (int i = head[x]; i != -1; i = edge[i].next)

29     {

30         int v = edge[i].v;

31         dfs(v);

32         for (int j = num[x]; j >= 0; j--)

33             for (int k = 1; k <= num[v]; k++)

34                 dp[x][j+k] = max(dp[x][j+k], dp[x][j] + dp[v][k] - edge[i].w);

35         num[x] += num[v];//x           

36     }

37 }

38 int main()

39 {

40     //freopen("data.in", "r", stdin);

41     scanf("%d%d", &n, &m);

42     init_edge();

43     for (int i = 1; i <= n - m; i++)

44     {

45         num[i] = 0;//i           0

46         int k;

47         scanf("%d", &k);

48         while (k--)

49         {

50             int b, c;

51             scanf("%d%d", &b, &c);

52             addedge(i, b, c);

53         }

54     }

55     for (int i = 1; i <= n; i++)

56         for (int j = 1; j <= m; j++)

57             dp[i][j] = -inf;

58     for (int i = n - m + 1; i <= n; i++)

59     {

60         num[i] = 1;

61         scanf("%d", &dp[i][1]);

62     }

63     dfs(1);

64     for (int i = m; i >= 0; i--) if (dp[1][i] >= 0)

65     {

66         printf("%d
", i);

67         break;

68     }

69     return 0;

70 }