Codeforces 1084CD(DP思想 / 树形DP)

发表于 | 分类于 | | + s

Codeforces 1084C
题意：给定一个$n$长小写字母序列，找出只包含a的子序列，满足每两个a之间有b，求方案数。
DP思想。从后往前扫，对每个a维护从这个位置开始顺序，这个位置必选的合法序列数量。
对于更新，不妨用b将序列分块，每个a只能继承他右边最近的一块的值。然后自身还有一个贡献，累加即可。

Codeforces 1084D
题意：树上每个点有正权值$a_i$，每条边有负权值$W$，你可以随意选择一条路径，使得这条路径的总权值最大，要求每个点每条边至多都只能走一次。
一开始想得好偏……
然而就是个树形DP，设$dp(u)$为$u$子树中的某个点到$u$的路径最长权。则转移为
$dp(u)=max(dp(v)-W(u,v)+a_u)$，当且仅当$dp(v)-W(u,v) \leq 0$
然后这样最后要统计每个点的$dp$值取个$max$就行了
等等，路径不一定是”直”的。所以我们要在DP每个点的过程中合并两条路径来得到”弯”的路径

这里弯直的意思是可能存在下面的情况：

1
|
2
|
3

直：1-2-3

  1
  |
 / \
2   3

弯：2-1-3

知识点：
1、计数问题逃不了DP、组合数学
2、树上最优问题要像到DP，路径不要漏了弯的路径

1093C:

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky { 

    const LL MAXN = 100000 + 5, MO = 1e9 + 7;

    LL n;
    char s[MAXN];

    void clean() {
    }
    int solve() {
        clean();
        scanf("%s", s + 1ll);
        n = strlen(s + 1ll);
        LL ans = 0ll, tot = 0ll, lsttot = 0ll;
        for (LL i = n; i; --i) {
            if (s[i] == 'a') ans = (ans + lsttot + 1ll) % MO, tot = (tot + lsttot + 1ll) % MO;
            else if (s[i] == 'b' && tot) lsttot = (lsttot + tot) % MO, tot = 0ll;
        }
        cout << ans;
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

1093D:

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky { 

    const LL MAXN = 300000 + 5;

    LL ans, n, dp[MAXN], dw[MAXN];
    vector<LL > G[MAXN], W[MAXN];

    void ins(LL u, LL v, LL w) {G[u].push_back(v), W[u].push_back(w);}

    void dfs(LL u, LL fa) {
        dp[u] = dw[u];
        LL maxd = 0, cid = 0;
        for (LL i = 0; i < (LL)G[u].size(); ++i) {
            LL v = G[u][i], bw = W[u][i];
            if (v != fa) {
                dfs(v, u);
                if (dp[v] - bw >= 0ll) {
                    dp[u] = max(dp[u], dp[v] - bw + dw[u]);
                    if (dp[v] - bw > maxd) {
                        cid = maxd, maxd = dp[v] - bw;
                    } else if (dp[v] - bw > cid) {
                        cid = dp[v] - bw;
                    }
                }
            }
        }
        ans = max(ans, dw[u] + cid + maxd);// 合并两条路径
    }

    void clean() {
        ans = 0ll;
    }
    int solve() {
        clean();
        scanf("%lld", &n);
        for (LL i = 1; i <= n; ++i) scanf("%lld", &dw[i]);
        for (LL u, v, w, i = 1; i < n; ++i) {
            scanf("%lld%lld%lld", &u, &v, &w);
            ins(u, v, w), ins(v, u, w);
        }
        dfs(1, 0);
        for (LL i = 1; i <= n; ++i) ans = max(ans, dp[i]);
        cout << ans;
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------