문제 풀이:

처음에는 트리 DP가 밑에서 위로 업데이트되는 것을 생각했는데 아들이 많을 때 상황이 너무 많아서 고려할 수가 없었어요.
dfs 순서에 따라 나무의 점을 하나하나 염색할 수 있습니다.이렇게 한 노드 x를 염색할 때, 그의 아버지 노드는 이미 염색되었다.정의 상태 dp[i][j]dp[i][j]dp[i][j]는 dfs 서열의 전 ii 노드를 jj j 색상으로 염색하는 몇 가지 방안이 있습니까?ii i 결점 염색의 경우 다음 두 가지 옵션이 있습니다.
4

이전 i-3-1i-1i-3 1개의 결점을 사용한 색을 선택한다.그럼 이 결점에서 염색할 수 있는 색깔은 아버지가 염색한 색깔이 틀림없다.앞의 어느 결점과 염색이 같든 경로가 아버지의 결점을 지나기 때문이다.이렇게 선택하기 전 i-3-1i-1i-3 1개의 결점은 jj j 색상을 사용했다.전 i-3-1i-1i-3 1개의 결점 방안 수는 dp[i-31][j]dp[i-1][j]dp[i-31][j][j]각 방안은 dp[i][j]dp[i][j]dp[j]dp[i][j]만 대응한다

사용하지 않은 색상을 선택한다.이렇게 선택하기 전 i-3 1i-1 i-3 1개의 결점은 j-3 1j-1 j-3 1가지 색깔로 한다.전 i-3-1i-1i-3 1개의 결점 방안 수는 dp[i-3-1][j-3]dp[i-1][j-1]dp[i-3]dp[i-3][j-1]이다.각 전 i-1 방안에 대해 제j종 색깔의 선택은 k-3-j+1k-j+1k-3j+1종이 있기 때문에 각 전 i-1 방안은 k-3j+1k-j+1k-3j+1개 dp[i][j]dp[i][j]dp[i][j][j]에 대응하는 방안이다.이렇게 방정식을 옮기면 쓸 수 있다.주어진 나무 구조와는 아무런 관계가 없다는 것을 알 수 있다.

코드:

/**
* Author : Xiuchen
* Date : 2020-04-09-19.11.59
* Description : dfs  +     
*/
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
const ll mod = 1e9 + 7;
const int maxn = 310;
int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}
int n, k;
ll dp[maxn][maxn];
vector<int> G[maxn];
int main(){
    scanf("%d%d", &n, &k);
    int x, y;
    for(int i = 1; i <= n - 1; i++){
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= k; j++)
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] * (k - j + 1) % mod) % mod;
    }
    ll ans = 0;
    for(int i = 1; i <= k; i++) ans = (ans + dp[n][i]) % mod;
    printf("%lld
", ans);
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

제11회 산동성 대학생 프로그램 설계 경연대회 Adventurer's Guild(dp)

전송문 제목: 몬스터의 수량 n, 캐릭터의 생명력 H, 캐릭터의 공격 S 건네기;다음 n행, 매 행위 매 몬스터의 혈액량 h, 공격 s, 가치 w; 매번 몬스터를 처치할 때마다 h의 혈액량과 s의 공격을 소모한다. ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다