一点值得回看的今天做的树（shu)形(wei)dp记录
诡异数字
https://ac.nowcoder.com/acm/problem/20669
思路：dp[pos, pre, cnt]表示当前位置是pos,上一位出现的数是pre, 这个数出现cnt次的数量。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 25, mod = 20020219;
ll t ,l, r, n, numlim[N], num[N], dp[N][10][1010];
ll dfs(int pos, bool limit, bool lead, int pre, int cnt){
if(!pos) return 1;
if(!limit && !lead && ~dp[pos][pre][cnt]) return dp[pos][pre][cnt];
int up = limit ? num[pos] : 9;
ll ans = 0;
for(int i = 0; i <= up; ++ i){
if(lead && i == 0) ans = (ans + dfs(pos - 1, limit && i == up, true, -1, 0)) % mod;
else{
if(i == pre){
if(cnt == numlim[i]) continue;
else ans = (ans + dfs(pos - 1, limit && i == up, false, i, cnt + 1)) % mod;
}else ans = (ans + dfs(pos - 1, limit && i == up, false, i, 1)) % mod;
}
}
if(!limit && !lead) dp[pos][pre][cnt] = ans;
return ans;
}
ll solve(ll x){
memset(dp, -1, sizeof dp);
int pos = 0;
while(x){
num[++ pos] = x % 10;
x /= 10;
}
return dfs(pos, true, true, -1, 0);
}
int main(){
cin >> t;
while(t --){
cin >> l >> r >> n;
memset(numlim, 0x3f, sizeof numlim);
for(int i = 1; i <= n; ++ i){
ll x, cnt;
cin >> x >> cnt;
numlim[x] = min(numlim[x], cnt);
}
cout << (solve(r) - solve(l - 1) + mod) % mod << endl;
}
return 0;
}7的意志
https://ac.nowcoder.com/acm/problem/20665
再次证明牛客的星是xjb标的qwq 这是个锤子5星题
思路：用remain存这个数%7的值，sum存这个数每一位相加的和%7的余数。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 25;
ll l, r, dp[N][10][10];
int num[N];
ll dfs(int pos, bool limit, int sum, int remain){
if(!pos) return (sum % 7 == 0 && remain % 7 == 0);
if(!limit && ~dp[pos][sum][remain]) return dp[pos][sum][remain];
ll ans = 0;
int up = limit ? num[pos] : 9;
for(int i = 0; i <= up; ++ i) ans += dfs(pos - 1, limit && i == up, (sum + i) % 7, (remain * 10 + i) % 7);
if(!limit) dp[pos][sum][remain] = ans;
return ans;
}
ll solve(ll x){
int pos = 0;
while(x){
num[++ pos] = x % 10;
x /= 10;
}
return dfs(pos, true, 0, 0);
}
int main(){
memset(dp, -1, sizeof dp);
while(cin >> l >> r){
if(!l && !r) break;
cout << solve(r) - solve(l - 1) << endl;
}
return 0;
}树上子链
https://ac.nowcoder.com/acm/problem/202475
思路：类似树的最长路径求法， dp表示的是选择当前点的情况下能得到的最大单链的值（不能是折线形的， 否则没法推了）用ans实时更新答案（这时可能是折线形的）
tips:可能点权全是负的，所以ans初始化的时候不可以是0.
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100010, M = 2 * N, inf = 0x3f3f3f3f;
int idx, ne[M], e[M], h[N];
int n;
ll dp[N],ans = -1e12,w[N];
void add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++;}
void dfs(int u, int fa){
ll d1 = 0, d2 = 0;
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j == fa) continue ;
dfs(j, u);
if(dp[j] >= d1) d2 = d1, d1 = dp[j];
else if(dp[j] > d2) d2 = dp[j];
}
d1 += w[u];
dp[u] = d1;
ans = max(d1 + d2, ans);
}
int main(){
cin >> n;
memset(h, -1, sizeof h);
for(int i = 1; i <= n; ++ i) scanf("%lld", &w[i]);
for(int i = 1; i <= n - 1; ++ i){
int a, b;
scanf("%d%d",&a,&b);
add(a, b), add(b, a);
}
dfs(1, 1);
//for(int i = 1; i <= n; ++ i) printf("%d ", dp[i]);
cout << ans;
return 0;
}
/*
5
-1 -1 -1 -1 -1
1 2
2 3
3 4
4 5
-1
*/吉吉王国
https://ac.nowcoder.com/acm/problem/210473
思路：求最大边权最小， 而且最大边权有限制， 想到二分+树形dp check.
tips：这题只是要求最大边权最小， 没有要求总的最小， 要和Rinne Loves Edges 区分开。 详见代码注释的两组样例。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1010, M = 2 * N, inf = 0x3f3f3f3f;
int idx, ne[M], e[M], w[M], h[N];
int n,m,s;
ll dp[N];
void add(int a, int b, int c){ e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;}
void dfs(int u, int fa, int limit){
bool f = false;
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j == fa) continue ;
dfs(j, u, limit);
if(w[i] > limit) dp[u] += dp[j];
else dp[u] += min(dp[j], 1ll * w[i]);
f = true;
}
if(!f) dp[u] = inf;
}
int main(){
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 1; i <= n - 1; ++ i){
int a, b, c;
scanf("%d%d%d",&a,&b,&c);
add(a, b, c), add(b, a, c);
}
int l = 0, r = 1010;
while(l < r){
int mid = (l + r) >> 1;
memset(dp, 0, sizeof dp);
dfs(1, 1, mid);
if(dp[1] > m) l = mid + 1;
else r = mid;
//printf("mid = %d l = %d r = %d dp = %d\n", mid,l, r, dp[1]);
}
if(r == 1010) puts("-1");
else cout << r;
return 0;
}
/*
4 11
1 2 10
2 3 5
2 4 6
6
4 10
1 2 10
2 3 5
2 4 6
10
*/Cell Phone Network
https://ac.nowcoder.com/acm/problem/24953
AcWing 皇宫看守
注意被儿子覆盖的情况比较复杂，需要求出所有儿子的min(dp0, dp1)的和之后减掉当前选择的这个儿子的min,再加上在这个儿子放守卫的情况， 但是发现这个min的和就是已经求出的dp2
/*
dp状态转移方程：
0表示自己覆盖 dp(u,0) += min(dp[j,0],dp[j,1],dp[j,2])
1表示儿子覆盖(自己不放) 找出一个儿子，剩下的+min(dp[j,0],dp[j,1]) +
2表示父亲覆盖(自己不放) dp[u,2] += min(dp[j,0], dp[j,1])
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 10010, M = 2 * N;
int idx,ne[M],e[M],h[N],dp[N][3],n;
void add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++;}
void dfs(int u, int fa){
dp[u][0] = 1;
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j == fa) continue ;
dfs(j, u);
dp[u][0] += min(dp[j][0], min(dp[j][1], dp[j][2]));
dp[u][2] += min(dp[j][0], dp[j][1]);
}
dp[u][1] = 1e9;
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j == fa) continue ;
dp[u][1] = min(dp[u][1], dp[u][2] - min(dp[j][0], dp[j][1]) + dp[j][0]);
}
}
int main(){
cin >> n;
memset(h, -1, sizeof h);
for(int i = 1; i <= n - 1; ++ i){
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
dfs(1, 1);
cout << min(dp[1][0], dp[1][1]);
return 0;
}
Accumulation Degree
https://ac.nowcoder.com/acm/problem/51180
思路： 换根DP.
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 200010, M = 2 * N;
int idx, ne[M], e[M], h[N], in[N], w[M];
int n,m,t;
ll dp[N], dp2[N];
void add(int a, int b, int c){ e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;}
void dfs1(int u, int fa){
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j == fa) continue ;
dfs1(j, u);
if(in[j] == 1) dp[u] += w[i];
else dp[u] += min(dp[j], 1ll * w[i]);
}
}
void dfs2(int u, int fa){
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j == fa) continue ;
if(in[u] == 1) dp2[j] = w[i] + dp[j];
else dp2[j] = dp[j] + min(1ll * w[i], dp2[u] - min(dp[j], 1ll * w[i]));
dfs2(j, u);
}
}
void solve(){
idx = 0;
memset(h, -1, sizeof h);
memset(in, 0, sizeof in);
memset(dp, 0, sizeof dp);
cin >> n;
for(int i = 1; i <= n - 1; ++ i){
int a, b, c;
scanf("%d%d%d", &a,&b,&c);
add(a, b, c), add(b, a, c), in[a] ++, in[b] ++;
}
dfs1(1, 1);
dp2[1] = dp[1];
dfs2(1, 1);
//for(int i = 1; i <= n; ++ i) printf("%d ", dp2[i]);
ll ans = 0;
for(int i = 1; i <= n; ++ i) ans = max(ans, dp2[i]);
cout << ans << endl;
}
int main(){
cin >> t;
while(t --) solve();
return 0;
}
Tree
https://ac.nowcoder.com/acm/problem/19782
思路： 换根DP. 从下往上dfs的时候， 父亲的dp值 *= 儿子的dp + 1【这个1可以理解为这个子树的空集。如果所有子树都取空集，那就相当于之选当前这一个点】
从上往下dfs的时候有一个坑点， dp + 1有可能等于1e9 + 7， 这时没有逆元， 没法用快速幂+费马小求逆元， 所以我们可以暴力算得到该点的dp2. 注意dfs1就是暴力算以某个点为根的情况， 所以这里直接调用dfs1即可。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 10, M = 2 * N, mod = 1e9 + 7;
int idx, ne[M], e[M], h[N];
int n;
ll dp[N],dp2[N];
ll ksm(ll a, ll b){
ll res = 1;
while(b){
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
void add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++;}
void dfs(int u, int fa){
dp[u] = 1;
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j == fa) continue ;
dfs(j, u);
dp[u] = (dp[u] * (dp[j] + 1)) % mod;
}
}
void dfs2(int u, int fa){
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j == fa) continue ;
if((dp[j] + 1) % mod == 0){
dfs(j, j);
dp2[j] = dp[j];
}
dp2[j] = (dp[j] * (dp2[u] * ksm((dp[j] + 1), mod - 2) % mod + 1)) % mod;
dfs2(j, u);
}
}
int main(){
cin >> n;
memset(h, -1, sizeof h);
for(int i = 1; i <= n - 1; ++ i){
int a, b;
scanf("%d%d",&a,&b);
add(a, b), add(b, a);
}
dfs(1, 1);
dp2[1] = dp[1];
dfs2(1, 1);
for(int i = 1; i <= n; ++ i) printf("%d\n", dp2[i]);
return 0;
} 
投递虾皮信息等公司10个岗位 >
查看17道真题和解析
