hdu 5534(dp)

Input
The first line contains an integer 
T  indicating the total number of test cases.
Each test case starts with an integer 
n  in one line,
then one line with 
n−1  integers 
f(1),f(2),…,f(n−1) .
1≤T≤2015
2≤n≤2015
0≤f(i)≤10000
There are at most 
10  test cases with 
n>100 .
 
Output
For each test case, please output the maximum coolness of the completed tree in one line.
 
Sample Input

   
   
   
   

    
    
    
    2
3
2 1
4
5 1 4
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    5
19
   
   
   
   
   
   
   
   


   
   
   
   

제목: 솔직히 말해서 한참 동안 보았지만 제목을 이해하지 못했다.
n개의 점을 주고 n-1개의 변을 추가해야 합니다. 각 노드마다 도(입도+출도)가 있습니다. 도의 수량은 서로 다른 값에 대응하고 트리의 최대 값을 구합니다.
사고방식: 모두 2*(n-1)개의 도가 있다. 우선, 각 점마다 한 개의 도가 있고 나머지 n-2개의 도를 n개의 점에 분배하여 그것들을 가장 크게 한다.
그래서 배낭 문제가 되었다/*동규를 도저히 할 줄 모르니 배워야겠다
/*제목에서 그 순간을 이해하지 못하면 반드시 해낼 수 없다는 뜻으로 다른 사람의 보고서를 보러 갈 수밖에 없다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>
#include <algorithm>
#include <functional>

//       - -

using namespace std;

int a[20005];
int dp[20005];

int main()
{
    int cas,n;
    scanf("%d",&cas);
    while(cas -- )
    {
        scanf("%d",&n);
        for(int i = 0; i < n-1; i++)
            scanf("%d",a+i);
        int all = n-2;
        int ans = a[0]*n;

        for(int i = 1; i <= n; i++)
            dp[i] = -0x3f3f3f3f;
        dp[0]= ans;
        for(int i = 1; i < n-1; i++)
            a[i] -= a[0];

        for(int i = 1; i <= all; i++)
        {
            for(int j = i; j <= all; j++)
            {
                dp[j] = max(dp[j],dp[j-i] + a[i]);
            }
        }
        printf("%d
",dp[all]);
    }
    return 0;
}