【hdu 5534】【2015 ACM/IPCCアジア区長春駅】Partial Tree題意＆題解＆コード

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=5534 題意:n個のノードの数を1本構築し、f[i]は度数(入度+出度)がiのノードの点権を表し、すべてのf[i]を与え、この木の最大点権を問う.問題解:1本のdp問題、思惟はとても巧みで全部でn個の点があって総度数は2です×(n-1)まず各点について少なくとも一度はこの決定された一度を各点に割り当てておき、次にn-2度が割り当てられていないことが残っている.度数は任意に割り当てられているからである.次に、問題として、n-2度を任意の複数のn-2度、n-3度、n-4度......1度が割り当て終わった後の重み値を最大にすると見なすことができる.これは完全なリュックサックではないでしょうか.やはり私はdpが下手です.コード:

#include
#include
#include
#include
using namespace std;
int n,T,f[2020],dp[4050];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for (int i=1;iscanf("%d",&f[i]);
            dp[i]=-1;
        }
        dp[0]=f[1]*n;
        int now=f[1];
        for (int i=1;ifor (int i=1;ifor (int j=0;j<=n-2;j++)
            if (j-i>=0)
            dp[j]=max(dp[j],dp[j-i]+f[i+1]);
        }
        cout<2]<