HDU 1011 트리 백팩(DP) Starship Troopers
2425 단어 oop
제목: 지도에 몇 개의 방이 있는데 각 방마다 일정한 버그가 있고 브레인스를 받을 가능성치가 있다. 한 사람이 m지군을 이끌고 입구(방1)로 들어간다.
어떤 방에 도착해서 버그를 모두 죽여야만 상응하는 값을 얻을 수 있다.최대 가능성치를 얼마나 얻을 수 있느냐고 물었다.
PS 1). 한 군대는 20bugs를 죽일 수 있지만, 한 군대가 전쟁을 일으킨 후에는 다시는 다른 곳으로 갈 수 없다
2) . 되돌아갈 수 없다
분석: [나무 가방]은 dp[i][j]로 방 i에 도착한 군대 수가 j일 때 방 i와 그와 연결된 방에서 모두 획득한 값을 나타낸다.
dp[j][k]=max(dp[j][k], dp[j][k-t]+dp[jv][t])(그중 jv는 j와 인접한 방)
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf = 0x7FFFFFFF;
const int maxn = 111;
struct node{
int v;
node *next;
}tree[maxn<<1], *head[maxn];
int ptr,n;
int dp[105][2005], bug[105], w[105];
bool vis[105];
void Init(){
ptr=1;
memset(head,0,sizeof(head));
memset(dp,0,sizeof(dp));
memset(vis,false,sizeof(vis));
}
void AddEdge(int a,int b){
tree[ptr].v=b;
tree[ptr].next=head[a];
head[a]=&tree[ptr++];
}
int DFS(int cnt,int M){
if(M==0) return 0;
int m=M-bug[cnt];
vis[cnt]=true;
node *p=head[cnt];
int Max=0;
while(p!=NULL){
if(vis[p->v]){
p = p->next; continue;
}
for(int i=m;i>=bug[p->v];--i)
dp[p->v][i] = DFS(p->v,i);
for(int i=m;i>=bug[p->v];--i)
for(int j=i;j>=bug[p->v];--j)
dp[cnt][i]=max(dp[cnt][i],dp[cnt][i-j]+dp[p->v][j]);
p=p->next;
}
return w[cnt]+dp[cnt][m];
}
int main(){
int m;
while(~scanf("%d%d",&n,&m)&&!(n==-1&&m==-1)){
Init();
for(int i=1;i<=n;++i){
int a; scanf("%d%d",&a, w+i);
bug[i]=(a%20)?1:0;
bug[i]+=a/20;
}
for(int i=1;i<n;++i){
int a,b; scanf("%d%d",&a,&b);
AddEdge(a,b);
AddEdge(b,a);
}
if(m<bug[1]){
puts("0"); continue;
}
printf("%d
", DFS(1,m) );
}
return 0;
}
.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
핸들러 - 작은 구현이 좋은 이유는 무엇입니까?핸들러는 단순히 입력을 받아들이고, 가능한 경우 수신된 입력 데이터로 진행할지 선택적으로 결정하고, 입력을 적절한 형식으로 변환하고, 기본 프로시저를 호출합니다. 사용자/클라이언트는 사용자 인터페이스나 REST, 메...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.