트 리 dp hdu - 4616 - Game

5980 단어 game
제목 링크:
http://acm.hdu.edu.cn/showproblem.php?pid=4616
제목 의 대의:
나무 한 그루 에 게 각 노드 에 선물 값 과 trick 가 있 는 지, 한 노드 에 올 때마다 선물 을 받 아야 합 니 다. 만약 에 이 노드 에 trick 가 있 으 면 안 티 trick 기 회 를 낭비 합 니 다. 만약 에 처음에 C 번 의 안 티 trick 기회 가 있 으 면 가장 많은 선물 을 받 을 수 있 는 지 물 어보 면 기 회 는 다 쓴 후에 끝 납 니 다.방문 한 노드 는 다시 방문 할 수 없습니다.
문제 풀이 방향:
나무
나무 모양 dp 는 아 아 아 아 아 아 아 아 아...
dp [i] [j] [0] 은 노드 i 부터 j 번 의 기회 가 있 고 서브 트 리 에서 가장 큰 선물 을 받 을 수 있 는 값 을 나타 낸다.
dp [i] [j] [1] 은 노드 i 부터 j 번 의 기회 가 있 고 서브 트 리 에서 큰 선물 을 받 을 수 있 는 값 을 나타 낸다.
by [i] [j] 는 i 노드 를 표시 하고 j 번 의 기회 가 있 을 때 가장 큰 값 을 얻 은 직접 아들 레이 블 을 표시 합 니 다.
먼저 임의의 점 을 뿌리 로 하고 dfs 를 한 번 합 니 다.각 노드 에서 시 작 된 하위 트 리 의 최대 값 과 차 대 치 를 구하 십시오.
같은 점 을 루트 로 하고 dfs 를 한 번 더 하면 파 라 메 터 는 아버 지 를 시작 으로 하 는 노드 를 유지 하고 이 노드 의 최대 치 를 거치 지 않 습 니 다.이 노드 에서 출발 하 는 나무 전체 에서 의 최대 치 를 구하 십시오.
PS:
이 문제 가 번 거 로 운 점 은 기회 가 마침 다 떨 어 졌 을 때 게임 이 끝나 면 뒤의 0 기회 치 를 누적 해 서 는 안 된다 는 것 이다.
따라서 이 노드 에 trick 가 있 는 지 여 부 를 나 누 어 판단 해 야 합 니 다. trick 가 있 으 면 j > = 2 시 에 만 뒤에서 업 데 이 트 됩 니 다.
PS2: 트 리 dp 를 많이 만들어 야 지.
코드:
 
#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<string>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<stack>

#include<list>

#include<queue>

#define eps 1e-6

#define INF 0x1f1f1f1f

#define PI acos(-1.0)

#define ll __int64

#define lson l,m,(rt<<1)

#define rson m+1,r,(rt<<1)|1

//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;





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

//freopen("data.out","w",stdout);



#define Maxn 55000

ll dp[Maxn][5][2]; //dp[i][j][0]   i     j   ,           

int tra[Maxn],val[Maxn],cnt,n,c;

int by[Maxn][5];

ll ans;



struct Edge //   

{

   int v;

   struct Edge * next;

}edge[Maxn<<1],*head[Maxn<<1];



void add(int a,int b)

{

   ++cnt;

   edge[cnt].v=b,edge[cnt].next=head[a];

   head[a]=&edge[cnt];

}

ll Max(ll a,ll b)

{

   return a>b?a:b;

}

void dfs1(int pre,int cur)

{

   struct Edge * p=head[cur];

   bool flag=true;

   while(p)

   {

      if(p->v!=pre)

      {

         flag=false;

         dfs1(cur,p->v); //        

         if(tra[cur]) //    trick

         {

            dp[cur][1][0]=val[cur];

            for(int i=2;i<=c;i++) //      2           

            {

               if(dp[p->v][i-1][0]+val[cur]>=dp[cur][i][0])

               {

                  dp[cur][i][1]=dp[cur][i][0];//    

                  dp[cur][i][0]=dp[p->v][i-1][0]+val[cur];

                  by[cur][i]=p->v;

               }

               else if(dp[p->v][i-1][0]+val[cur]>dp[cur][i][1])

               {  //    

                  dp[cur][i][1]=dp[p->v][i-1][0]+val[cur];

               }

            }

         }

         else

         { //    trick,           

            for(int i=0;i<=c;i++)

            {

               if(dp[p->v][i][0]+val[cur]>=dp[cur][i][0])

               {

                  dp[cur][i][1]=dp[cur][i][0];

                  dp[cur][i][0]=dp[p->v][i][0]+val[cur];

                  by[cur][i]=p->v;

               }

               else if(dp[p->v][i][0]+val[cur]>dp[cur][i][1])

               {

                  dp[cur][i][1]=dp[p->v][i][0]+val[cur];

               }

            }

         }

      }

      p=p->next;

   }

   if(flag) //        

   {

      for(int i=tra[cur];i<=c;i++)

         dp[cur][i][0]=val[cur];

   }

}

void dfs2(int pre,int cur,ll *aa)

{

   ll MM=0;

   if(tra[cur])

   {

      MM=dp[cur][c][0];//     

      if(c>=2)

         MM=Max(MM,aa[c-1]+val[cur]); //    

   }

   else

      MM=Max(dp[cur][c][0],aa[c]+val[cur]);

   if(MM>ans)

      ans=MM;

  /* printf("cur:%d ans:%I64d 
",cur,MM); for(int i=0;i<=c;i++) printf("aa[%d]:%I64d ",i,aa[i]); putchar('
'); system("pause");*/ struct Edge * p=head[cur]; while(p) { if(p->v!=pre) { ll tt[5]={0}; //tt[i] i if(tra[cur]) { tt[1]=dp[cur][1][0]; // for(int i=2;i<=c;i++) { if(p->v!=by[cur][i]) // , tt[i]=Max(aa[i-1]+val[cur],dp[cur][i][0]); else tt[i]=Max(aa[i-1]+val[cur],dp[cur][i][1]); } } else { for(int i=0;i<=c;i++) { if(p->v!=by[cur][i]) tt[i]=max(aa[i]+val[cur],dp[cur][i][0]); else tt[i]=max(aa[i]+val[cur],dp[cur][i][1]); } } /* for(int i=0;i<=c;i++) printf("i:%d %d
",i,tt[i]);*/ dfs2(cur,p->v,tt); } p=p->next; } } int main() { int t,a,b; //freopen("1006.in","r",stdin); //freopen("1006ans.out","w",stdout); scanf("%d",&t); while(t--) { scanf("%d%d",&n,&c); memset(by,-1,sizeof(by)); memset(head,NULL,sizeof(head)); for(int i=0;i<n;i++) scanf("%d%d",&val[i],&tra[i]); cnt=0; for(int i=1;i<n;i++) { scanf("%d%d",&a,&b); add(a,b); add(b,a); } memset(dp,0,sizeof(dp)); ans=0; dfs1(-1,0); ll tt[5]={0}; dfs2(-1,0,tt); printf("%I64d
",ans); } return 0; }

 

좋은 웹페이지 즐겨찾기