[Codeforces] 855C. Helga Hufflepuff's Cup
題目連結:http://codeforces.com/contest/855/problem/C
賽中看到一堆大大們都寫出來的題目,但是自己怎麼寫都寫不出來就是了QQ,一定是因為我DP太爛的緣故
總之這題很明顯就是個樹DP題,狀態這裡是定成$$ dp[i][x][0] := 第i個節點放[1,k-1]種類且有x個k的方法數 \\ dp[i][x][1] := 第i個節點放k且有x個k的方法數 \\ dp[i][x][2] := 第i個節點放[k+1,M]且有x個k的方法數 $$轉移的話就算滿好想的了,大致就是0號可以從0,1,2轉來;2只能從0轉來;ㄉ可以從0, 2轉來,而怎麼轉就直接枚舉其中一邊有幾個就好了。
賽中看到一堆大大們都寫出來的題目,但是自己怎麼寫都寫不出來就是了QQ,一定是因為我DP太爛的緣故
總之這題很明顯就是個樹DP題,狀態這裡是定成$$ dp[i][x][0] := 第i個節點放[1,k-1]種類且有x個k的方法數 \\ dp[i][x][1] := 第i個節點放k且有x個k的方法數 \\ dp[i][x][2] := 第i個節點放[k+1,M]且有x個k的方法數 $$轉移的話就算滿好想的了,大致就是0號可以從0,1,2轉來;2只能從0轉來;ㄉ可以從0, 2轉來,而怎麼轉就直接枚舉其中一邊有幾個就好了。
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
typedef long long lld;
const int N = 100000 + 5;
const int K = 10 + 2;
const int MOD_BASE = 1e9+7;
int n, m, k, x;
lld dp[N][K][3];
vector<int> G[N];
void dfs(int,int);
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
for(int i=0;i<n-1;i++){
int u, v; cin>>u>>v;
G[u].PB(v);
G[v].PB(u);
}
cin>>k>>x;
dfs(1, 1);
lld ans = 0;
for(int i=0;i<=x;i++){
ans=(ans+dp[1][i][0])%MOD_BASE;
ans=(ans+dp[1][i][1])%MOD_BASE;
ans=(ans+dp[1][i][2])%MOD_BASE;
}
cout<<ans<<'\n';
return 0;
}
void dfs(int w, int f){
dp[w][1][1]=1;
dp[w][0][0]=k-1;
dp[w][0][2]=m-k;
for(auto i: G[w]){
if(i==f) continue;
dfs(i, w);
lld ndp[K][3]={0};
for(int kk=0;kk<=x;kk++){
for(int j=0;j<=kk;j++){
ndp[kk][0] = (ndp[kk][0]+(dp[w][j][0]*dp[i][kk-j][0])%MOD_BASE)%MOD_BASE;
ndp[kk][0] = (ndp[kk][0]+(dp[w][j][0]*dp[i][kk-j][1])%MOD_BASE)%MOD_BASE;
ndp[kk][0] = (ndp[kk][0]+(dp[w][j][0]*dp[i][kk-j][2])%MOD_BASE)%MOD_BASE;
ndp[kk][1] = (ndp[kk][1]+(dp[w][j][1]*dp[i][kk-j][0])%MOD_BASE)%MOD_BASE;
ndp[kk][2] = (ndp[kk][2]+(dp[w][j][2]*dp[i][kk-j][0])%MOD_BASE)%MOD_BASE;
ndp[kk][2] = (ndp[kk][2]+(dp[w][j][2]*dp[i][kk-j][2])%MOD_BASE)%MOD_BASE;
}
}
for(int ii=0;ii<=x;ii++){
for(int j=0;j<3;j++){
dp[w][ii][j]=ndp[ii][j];
}
}
}
}
留言
張貼留言