Codeforces 77C 트리 dp + 욕심
제목:
n개 점을 지정,
점당 콩 수량
아래는 나무입니다.
다시 시작점을 드리도록 하겠습니다.
점마다 그 점을 찍은 콩을 하나씩 먹는다.
물음: 출발점으로 돌아가면 최대 몇 알의 콩을 먹을 수 있느냐
사고방식: 트리 dp
현재 노드 u에 대해 먼저 하위 노드 v를 모두 한 번 걸어라.
그리고 u시에 콩이 없거나 v시에 콩이 없을 때까지 (u, v) 사이를 왕복한다.
dp[u]는 u점의 최대치를 나타낸다.a[u]는 u점에 남은 콩의 수다.
#include
#include
#include
#include
using namespace std;
#define N 100002
#define ll long long
int n, root;
vectorG[N];
bool cmp(int a, int b){return a>b;}
int a[N];
ll dp[N];//dp[i] i
void dfs(int u, int fa){
dp[u] = 1;
vectors;
for(int i = 0; i < G[u].size(); i++)
{
int v = G[u][i]; if(v == fa || a[v] == 0)continue;
a[v]--;
dfs(v, u);
if(dp[v])
s.push_back(dp[v]);
}
sort(s.begin(), s.end(),cmp);
for(int i = 0; a[u] && i < s.size(); i++) a[u]--, dp[u] += s[i] +1;
for(int i = 0; a[u] && i < G[u].size(); i++)
{
int v = G[u][i]; if(v == fa || a[v] == 0)continue;
dp[u] += 2LL * min(a[u], a[v]);
a[u] -= min(a[u], a[v]);
}
}
int main() {
int i, u, v;
while(~scanf("%d", &n)) {
for(i = 1; i <= n; i++) scanf("%d",&a[i]), G[i].clear();
for(i = 1; i < n; i++)
{
scanf("%d %d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
scanf("%d",&root);
dfs(root, root);
cout< 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
확률 dp- Ilya and Escalatorcf518D는 대체적으로 n개인으로 구성된 대기열을 의미한다. 각 단위의 시간에 대기열 헤더는 대기열 확률이 p이거나 대기열을 나가지 않을 수 있다. 확률은 1-p이다. t단위의 시간에 대기열을 나가는 인원수에 대한...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
