트 리 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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
React를 사용한 브라우저 게임이 게시물은 코드에 들어가지 않고 어떻게 수행되었는지 간략하게 설명합니다. 소스 코드를 볼 수 있습니다 플래피 버드와 같은 장애물 회피 게임은 비교적 쉽게 시도할 수 있었습니다. 우주 테마를 추가하고 수직으로 만들면...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.