hdu 1011 Starship Troopers_나무
1813 단어 oop
제목: 나무 한 그루(뿌리 노드에서 출발해야 함)를 드리겠습니다. 노드마다 버그와value가 있습니다. 당신은 m명의 기사가 있습니다. 기사마다 20개의 버그를 처치할 수 있습니다. 이 노드의 모든 버그를 처치해야 이 노드의value를 얻을 수 있습니다. 최대value가 얼마인지 물어보세요.
사고방식: 전형적인 가방 dp, dp[n][m]=max(dp[n][m-x]+value, dp[n][m])
#include<iostream>
#include<cstdio>
using namespace std;
#define N 110
#define INF 999999999
struct node
{
int v,next;
}edge[N<<1];
int adj[N],vis[N],room[N][2],dp[N][N],edgeNum;
int max(int a,int b){return a>b?a:b;}
void AddEdge(int u,int v)
{
edge[edgeNum].v=v,edge[edgeNum].next=adj[u],adj[u]=edgeNum++;
edge[edgeNum].v=u,edge[edgeNum].next=adj[v],adj[v]=edgeNum++;
}
void init()
{
memset(vis,0,sizeof(vis));
memset(adj,-1,sizeof(adj));
memset(dp,0,sizeof(dp));
edgeNum=0;
}
void dfs(int u,int m)
{
int num=room[u][0]/20,i,j,k;
if(room[u][0]%20)//bug bug
num++;
vis[u]=1;
for(i=num;i<=m;i++)
dp[u][i]=room[u][1];//
for(i=adj[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(!vis[v])
{
dfs(v,m);
for(j=m;j>=num;j--)
{
for(k=1;j+k<=m;k++)
if(dp[v][k])
dp[u][k+j]=max(dp[u][k+j],dp[u][j]+dp[v][k]);//
}
}
}
}
int main()
{
int n,m;
int i,u,v;
while(scanf("%d%d",&n,&m))
{
if(n==-1&&m==-1)
break;
init();
for(i=1;i<=n;i++)
scanf("%d%d",&room[i][0],&room[i][1]);
for(i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
AddEdge(u,v);//
}
if(m==0)//
{
printf("0
");
continue;
}
dfs(1,m);// 1
printf("%d
",dp[1][m]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
핸들러 - 작은 구현이 좋은 이유는 무엇입니까?핸들러는 단순히 입력을 받아들이고, 가능한 경우 수신된 입력 데이터로 진행할지 선택적으로 결정하고, 입력을 적절한 형식으로 변환하고, 기본 프로시저를 호출합니다. 사용자/클라이언트는 사용자 인터페이스나 REST, 메...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
