hdu 5534

题目描述:n个节点度数之和为n-2，每个节点预分配了1个度，任意分配度数是否有可能形成树？

从1到n节点，考虑树的形状，考虑分配给当前节点i的度数，并且注意到当前节点的度数不会影响其他节点(之前或者之后)，因为之前先给每个节点分配1度的度数，然后n个节点度数之和确定，从1到n考虑，每个节点都有分配到0到n-2的度数的可能，还有n个节点的度数之和的为n-2的限制（某个节点分配到0个度，说明是叶子）。

求在y1+y2+.....+y[n-2]=(n-2)的条件下，F[y1]+F[y2]+.....F[y[n-2]]的最大收益；

其中xi代表i度的有几个，f[i]代表i度的收益；

将n-2个度分为n份,可以想象一条长度为n-2的线段，切成n段，获得的收益为F[len]，求收益最大？每段的长度的取值范围为0到n-2，那么可以这样考虑,最优情况下,一厘米长度的有几个？2厘米长度的有几个？3厘米长度的有几个？......n-2厘米长度的有几个？

数学形式为在x1+x2+....+x[n-2]=(n-2)的条件下，求x1*f[1]+x2*f[x2]+...x[n-2]*f[n-2]的最大值？

其次还需处理线段长度合并时权值的变化，消除的思想。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cmath>

#define maxn 2200

#define inf 0x3f3f3f3f3f3f

using namespace std;

int T,n,f[maxn];  //f代表石子的重量

int d[maxn];

int f1;

void init()

{

    for(int i=;i<maxn;i++)

        d[i]=-inf;

    d[]=;

}

void solve() //可以理解成切线段

{

    int ans=n*f1;

    for(int i=;i<=n-;i++)  //度数为i的有多少个

    {

       for(int j=i;j<=n-;j++)

       {

              if(d[j-i]+f[i] > d[j] )

               {

                   d[j]=d[j-i]+f[i];

               }

       }

    }

    ans+=d[n-];

     printf("%d\n",ans);

}

int main()

{

   // freopen("test.txt","r",stdin);

    scanf("%d",&T);

    while(T--)

    {

       scanf("%d",&n);

       scanf("%d",&f1);

       for(int i=;i<=n-;i++)

       {

           scanf("%d",&f[i]);

           f[i]-=f1;

       }

       init();

       solve();

    }

    return ;

}

巴特西

hdu 5534

最新文章

热门文章