트 리 DP 개인 총화
5363 단어 트 리 dp
대 신의 좋 은 글:https://blog.csdn.net/txl199106/article/details/45373507
대 신의 좋 은 글:https://blog.csdn.net/txl199106/article/details/45372337
나무 모양 dp 는 언제 사용 합 니까?
4. 567917. 제목 이 묘사 한 데이터 구조 가 나무 인지, 동적 계획 의 요 구 를 만족 시 키 는 지 판단 한다.그렇지 않 으 면 방법 을 바 꿔.
어떤 문제 가 동적 계획 의 요 구 를 만족 시 킵 니까?
하위 문제 의 최 우선 해결 도 전체 국면 에서 가장 좋 은 해결 이 고 무 후 효성, 다단 계 결정 문 제 를 만족시킨다.문 제 를 우선 몇 개의 키 문제 로 나 누 어 모든 키 문제 에서 하 다. 결판 을 내다 책, 동태 계획 은 다단 계 결정 을 해결 하 는 가장 좋 은 방법 이다.
단계: 주어진 문제 의 과정 을 시간 이나 공간 (나무 귀 중 은 공간, 즉 층수) 특징 에 따라 몇 가지 서로 연 결 된 단계 로 분해 하여 순서에 따라 각 단 계 를 구하 도록 한다. 단락 의 해석. 상태: 각 단계 가 시 작 될 때의 객관 적 인 조건 을 상태 라 고 한다. 의사 결정: 각 단락 의 상태 가 정 해 지면 서로 다른 결정 을 내 려 다음 단계 의 상 태 를 확정 할 수 있 는데 이런 결정 을 결정 이 라 고 한다.(즉, 아이 노드 와 아버지 노드 의 관계) 전략: 시작 에서 종점 까지 의 전 과정 에서 각 단계 의 결정 으로 구 성 된 결정 서열 을 전 과정 전략 이 라 고 부 르 고 전략 이 라 고 부른다. 상태 이동 방정식: 전 단계 의 종점 은 바로 후 단계 의 출발점 이다. 전 단계 의 결정 선택 은 후 단계 의 상 태 를 도 출 했다. 이런 관 계 는 k 단계 에서 k + 1 단계 까지 묘사 했다. 세그먼트 (나무 에서 아이 노드 와 아버지 노드) 상태의 변천 규칙 을 상태 전이 방정식 이 라 고 한다. 목표 함수 와 최적화 개념: 목표 함 수 는 다단 계 의사 결정 과정의 우열 을 평가 하 는 준칙 이다.가장 최 적 화 된 개념 은 일정한 조건 하에 서 하나의 경 로 를 찾 아 제목 의 구체 적 인 성질 에 따라 확 정 된 연산 을 거 친 후에 전 과정의 총 효 익 을 최 우선 에 이 르 게 하 는 것 이다.
4. 567917. 나무의 저장 방식: 노드 수가 5000 보다 적 으 면 인접 행렬 로 나 무 를 저장 하고 더 크 면 인접 표 로 저장 하 며 인접 표 의 저장 은 일반적인 상황 에서 vector 배열 로 저장 합 니 다.이 진 트 리 나 이 진 트 리 를 여러 갈래 로 돌려 야 한다 면 1 차원 배열 로 저장 할 수 있다
4. 567917. 상태 dp 방정식 을 작성 합 니 다. 두 가지: a. 뿌리 에서 잎 b. 잎 에서 뿌리 까지 뿌리 의 서브 노드 는 유용 한 정 보 를 뿌리 에 전달 하여 가장 좋 은 결 과 를 얻 을 수 있 습 니 다
나무의 특징 및 성질:
4. 567917. n 개의 점 이 있 고 n - 1 개의 변 의 무방 향도 가 있 으 며 임의의 두 개의 정점 사이 에 도달 할 수 있다
4. 567917. 무 방향 그림 에서 임 의 두 점 사이 에 있 고 길 은 하나 밖 에 없다
4. 567917. 한 점 에서 한 개의 선구자 가 있 지만 여러 개의 후계 가 있 을 수 있다
4. 567917. 방향 이 없 는 그림 은 고리 가 없다
Anniversary party
POJ - 2342
먼저 주제 의 뜻 을 이해 합 니 다. 어떻게 선택 하면 최종 적 으로 얻 을 수 있 는 즐거움 이 가장 큽 니까?제목 요구: 부하 직원 과 그의 직접 지도 자 는 함께 선택 할 수 없다.다음은 샘플 을 살 펴 보 겠 습 니 다. n, 아래 n 줄 을 입력 하고 각 줄 은 한 사람 이 대응 하 는 기쁨 치 를 대표 하 며 n - 1 줄 은 대응 하 는 관 계 를 나타 내 고 0 입력 으로 끝 납 니 다.
사고: 큰 신 이 준 절차 에 따라 먼저 이 문 제 는 데이터 구조 가 나무 에 대응 하 는 관계 인지 주관 관계 에 따라 해당 나무의 관 계 를 만족 시 킬 수 있 는 지 판단 할 수 있다.동적 계획 문제 입 니까?
동적 계획 의 요 구 를 만족 시 키 고 최대 즐거움 치, 후 효성 이 없 으 며 가장 잘 풀 리 고 문제 가 있다.그 다음 에 상 태 를 분석 하면 모든 상 태 는 선택 과 선택 하지 않 는 두 가지 상태 가 있 고 그 어떠한 점 의 취사선택 도 두 가지 상태 가 있다. dp [i] [0] 은 제 i 개인 이 선택 하지 않 은 최대 즐거움 치 를 나타 내 고 dp [i] [1] 은 제 i 개인 이 선택 한 최대 즐거움 치 를 나타 낸다.
dp[node][0]+=max(dp[i][0],dp[i][1]),dp[node][1]+=dp[i][0];저장 방식: 노드 수량 이 5000 개 남 았 으 니 인접 표 로 저장 하 는 것 이 좋 습 니 다. vector 로 저장 하 는 것 을 권장 합 니 다.
#include
#include
#include
#include
using namespace std;
const int maxn=6001;
int n;
int dp[maxn][3];
//dp[i][0] i
//dp[i][1] i
int father[maxn];
int vis[maxn];
void dfs(int node)
{
vis[node]=1;
for(int i=1;i<=n;i++)
{
if(!vis[i]&&father[i]==node)//i node
{
dfs(i);
dp[node][0]+=max(dp[i][0],dp[i][1]);
dp[node][1]+=dp[i][0];
}
}
}
int main()
{
while(cin>>n)
{
memset(dp,0,sizeof(dp));
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
{
cin>>dp[i][1];
dp[i][0]=0;
}
int son,fath,root;
bool beg=1;
root=0;
while(cin>>son>>fath,son||fath)
{
father[son]=fath;
if(root==beg||son)
{
root=fath;
}
}
while(father[root])//
root=father[root];
dfs(root);
int ans=max(dp[root][0],dp[root][1]);
printf("%d
",ans);
}
return 0;
}
Strategic game POJ - 1463
사실 이 문 제 는 이전 문제 의 유형 과 매우 비슷 하 다. 동적 계획 방정식 은 모두 비슷 하고 원리 도 기본 적 인 것 처럼 방법 일 뿐 vector 방법 을 사용한다.
사고, 동적 계획 의 요 구 를 만족 시 키 는 지, 트 리 구조 인지, 그 다음 에 저장 방식 을 고려 합 니 다. vector 가 인접 표 와 유사 하 든 1 차원 배열 로 대체 하 든 모두 가능 합 니 다.그 다음 에 동적 계획 방정식 을 고려 하면 똑 같이 두 가지 상태 가 있다. dp [node] [0] 는 node 를 뿌리 로 node 에 병사 가 필요 로 하 는 최소 병사 수 를 배치 하지 않 는 다 고 밝 혔 다. dp [node] [1] 는 node 를 뿌리 로 node 에 병사 가 필요 로 하 는 최소 병사 수 를 배치 하 는 것 을 나타 낸다.i 는 node 의 아들, dp [node] [0] + = dp [i] [1], 아버 지 는 위 에 놓 지 않 고 아들 은 위 에 꼭 놓 아야 합 니 다.제목 의 뜻 을 잘 보 세 요. 나무의 점 이 덮 여 있 는 문제 입 니 다.dp[node][1]+=min(dp[i][0],dp[i][1])。나 는 주로 결점 과 가장자리 의 세부 적 인 문 제 를 처리 하 는 것 이 어렵다 고 생각한다.
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn=1501;
vectormp[maxn];
ll dp[maxn][3];
ll father[maxn];
ll vis[maxn];
ll n;
void dfs(ll node)
{
dp[node][0]=0;
dp[node][1]=1;
//vis[node]=1;
// cout<<1<>n)
{
memset(dp,0,sizeof(dp));
memset(vis,0,sizeof(vis));
memset(father,-1,sizeof(father));
int fa,son,edge;
for(int i=0;i 좋은 웹페이지 즐겨찾기
