区间DP

POJ 1991 Turning in Homework

Posted on

/doge薛昊老是偷我题做,最近我也就拿他博客上的题来练练手。其中这道题真的什么思路都没有,这个区间DP的套路我还真没碰到过。

这是一个大区间推小区间的套路。

题意:
小明要在某层楼的各个老师那里交一大堆作业,但是小明来早了,老师还没上班,他站在这层楼的最左边,告诉你每个老师的上班时间,最后要在某个给定位置下楼,问最少时间。

思路:
shit,完全是看博客,看代码敲的。
一个比较困难的点在于给定离开地点,算了,不装了,就算取消这个条件我也写不来……
明确可以用dp求解,首先按照位置优先开门顺序次优的顺序排序,设三维数组 $dp[l][r][k]$。
当 $k=0$ 时,表示只有 $(l,r] $ 区间内的作业没有交。
而 $k=1$ 时,表示只有 $[l,r) $ 区间内的作业没有交。
而我们的其实状态$dp[1][n][0/1]$是已知的,我们完全可以由此不断向内挤压求出小区间的结果。
当 $l=r$ 时,则所有作业交完,且停在 $l$ 点。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
const int maxn = 1e3 + 5;
int dp[maxn][maxn][2];
pii point[maxn];

int getDis(int d, int s) { return point[d].first - point[s].first; }

int main()
{
    int n, h, b;
    scanf("%d %d %d", &n, &h, &b);
    range(i, 1, n) scanf("%d %d", &point[i].first, &point[i].second);
    sort(point + 1, point + 1 + n);
    fill(dp, 0x3f);
    dp[1][n][0] = max(point[1].first, point[1].second);
    dp[1][n][1] = max(point[n].first, point[n].second);
    rrange(len, 1, n - 1) range(l, 1, n + 1 - len)
    {
        int r = l + len - 1;
        if (l > 1) {
            dp[l][r][0] = min(dp[l][r][0], dp[l - 1][r][0] + getDis(l, l - 1));
            dp[l][r][1] = min(dp[l][r][1], dp[l - 1][r][0] + getDis(r, l - 1));
        }
        if (r < n) {
            dp[l][r][0] = min(dp[l][r][0], dp[l][r + 1][1] + getDis(r + 1, l));
            dp[l][r][1] = min(dp[l][r][1], dp[l][r + 1][1] + getDis(r + 1, r));
        }
        dp[l][r][0] = max(dp[l][r][0], point[l].second);
        dp[l][r][1] = max(dp[l][r][1], point[r].second);
    }
    int ans = inf;
    range(i,1,n) ans = min(ans,dp[i][i][0]+abs(b-point[i].first));
    printf("%d\n",ans);
    return 0;
}
树形DP

CodeForces 855 C Helga Hufflepuff’s Cup

Posted on

前几天的上分场的树形DP

我敢说思路和我当时想得已经一模一样了,还有半个多小时的时候,gou bi 带鱼说把题目给他看一下,然后立马得出,树形DP解不了,肯定是树分治!
当时我在一个子问题上走不出来,于是就信了,然后开始划水……

md

题意:
给你一棵树,要你给树上的每一个节点赋值,赋值存在范围,再给你一个特殊值,除开特殊值意外的数值赋值次数不限,但是特殊值的相邻节点的值不能是特殊值,也不能是比特殊值大的值。
问方案数。

思路:
首先值得注意的是,特殊值赋值次数不超过10,这是一个重要突破口,这使得树形DP的解法存在可能性。
简单说就是在每个节点都保存当前节点为根节点的子树分别含有 [ 0, 10 ] 个特殊值的方案数。
但这还不好决策转移,我们还需要对当前值的范围作为状态进行判断。
我在比赛中只用了,当前值为特殊值,和不是特殊值两个状态,但是现在看了其他人的代码,发现三个状态更容易。
当前节点赋值小于特殊值,大于特殊值,等于特殊值。这样就很好转移,不细说,看代码都能秒懂。

我在比赛时候被卡的子问题是这样的,对于计算当前子树的特殊值数量为 n 的时候,我必须将当前根节点的每一个孩子的状态都理清楚。
比如说数量为 3 ,有三个孩子A,B,C
那么其方案数就是以下情况累加

  • \( A_0+B_0+C_3 \)
  • \( A_0+B_3+C_0 \)
  • \( A_3+B_0+C_0 \)
  • \( A_1+B_0+C_2 \)
  • \( A_0+B_1+C_2 \)
    ……
    ……

:wc 好多,复杂度好高,这不是组合问题么???
现在看来真是煞笔……

AC Code

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;

int n, m, k, x;
vector<int> tree[maxn];

ll dp[maxn][3][11];
ll tmp[3][11];

void dfs(int u, int par)
{
    dp[u][0][0] = k - 1;
    dp[u][1][0] = m - k;
    dp[u][2][1] = 1;
    for (auto v : tree[u]) {
        if (v != par) {
            dfs(v, u);
            memset(tmp, 0, sizeof tmp);
            for (int i = 0; i <= x; i++)
                for (int j = 0; i + j <= x; j++) {
                    tmp[0][i + j] = (tmp[0][i + j] + dp[u][0][i] * (dp[v][0][j] + dp[v][1][j] + dp[v][2][j])) % mod;
                    tmp[1][i + j] = (tmp[1][i + j] + dp[u][1][i] * (dp[v][0][j] + dp[v][1][j])) % mod;
                    tmp[2][i + j] = (tmp[2][i + j] + dp[u][2][i] * dp[v][0][j]) % mod;
                }
            for (int i = 0; i <= x; i++)
                for (int j = 0; j < 3; j++)
                    dp[u][j][i] = tmp[j][i];
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    int u, v;
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &u, &v);
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    scanf("%d%d", &k, &x);
    dfs(1, 0);
    int ans = 0;
    for (int i = 0; i <= x; i++)
        for (int j = 0; j < 3; j++)
            ans = (ans + dp[1][j][i]) % mod;
    printf("%d\n", ans);
    return 0;
}
树形DP

CodeForces 19E Fairy

Posted on

一道二分图性质的应用 + 树形DP ?

看博客里都说是树形DP,但我觉得应该是树上前缀和更加合适一些

题意:
给你一个图,让你删除一条边,使得剩下的图是二分图。
输出可删边数并顺序输出边的序号。

思路:
首先你必须知道判定二分图的充要条件 —— 不存在奇环。
如果只是让你判定二分图的话,倒是随便搜一遍就可以解决的问题。
但是这里必须让你删掉一条边……

写不来……感觉不好写,最后无奈去看题解了……

先整理一下判断思路:

  1. 如果不存在奇环,那么原图本来就是一张二分图,每一条边都满足条件
  2. 覆盖了所有的奇环,并且不能覆盖偶环的所有边

为什么同时不能覆盖偶环,这个我还真没想到,但是在纸上画一画就是很显然的了,同时覆盖奇环和偶环的边删去后,两个环会变成一个新的环,偶数+奇数 还是奇数。所以不能覆盖偶环。

因此得出如下具体实现,随便生成一棵生成树,用树上前缀和计算出每一条树边覆盖的奇环数和偶环数。
如果奇环数量大于 1 ,那么非树边必定不可能是满足条件的,因为非树边最多只能覆盖一个环,两个及以上就是重边了。因此非树边只有在奇环数量等于 1 的时候才需要我们去考虑,如果该非树边覆盖了奇环,则删之。
而对于树边,判断其覆盖奇环数和偶环树是否满足条件即可。

AC Code

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;

const int maxn = 1e6 + 5;
const int maxm = 2e6 + 5;
int n, m, top, cnt;

pii edges[maxm];
int head[maxn];
int idx;

int odd[maxn], even[maxn];
int dep[maxn], edge_type[maxm];
bool vis[maxn];

void addEdge(int u, int v)
{
    edges[idx] = make_pair(v, head[u]);
    head[u] = idx++;
    edges[idx] = make_pair(u, head[v]);
    head[v] = idx++;
}

void dfs(int u, int e)
{
    vis[u] = true;
    dep[u] = ++top;
    int v;
    for (int id = head[u]; ~id; id = edges[id].second) {
        if (edge_type[id] == -1)
            continue;
        v = edges[id].first;
        if (!vis[v]) {
            edge_type[id] = edge_type[id ^ 1] = -1;
            dfs(v, id >> 1);
            odd[e] += odd[id >> 1];
            even[e] += even[id >> 1];
        } else {
            if (edge_type[id] == 1)
                odd[e]--;
            else if (edge_type[id] == 2)
                even[e]--;
            else {
                if ((dep[u] - dep[v]) & 1)
                    even[e]++, edge_type[id] = edge_type[id ^ 1] = 2;
                else
                    odd[e]++, edge_type[id] = edge_type[id ^ 1] = 1, cnt++;
            }
        }
    }
    top--;
}

int ans[maxn], anum;

int main()
{
    int u, v;
    scanf("%d %d", &n, &m);
    fill(head, head + n + 1, -1);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        addEdge(u, v);
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            dfs(i, 0);
    if (cnt == 0) {
        printf("%d\n", m);
        for (int i = 1; i <= m; i++)
            printf("%d ", i);
    } else {
        for (int i = 0; i < m; i++)
            if (odd[i] == cnt && even[i] == 0)
                ans[anum++] = i;
            else if (cnt == 1 && edge_type[i << 1] == 1)
                ans[anum++] = i;
        printf("%d\n", anum);
        for (int i = 0; i < anum; i++)
            printf("%d ", ans[i] + 1);
    }
    return 0;
}
DP套DP

HDU 4899 Hero meet devil

Posted on

训练赛的DP套DP,关于DP套DP,以前记得好像做过一道。题目本身十分巧妙,但貌似不是很多。可能不是很好出题吧。
所谓DP套DP,就是我DP所需的状态也需要额外的DP求出来。简单说,就是我需要DP两次,在第一次的DP结果上再DP一次。

题意:
给你一个DNA序列,再给你一个固定长度,问你在这个长度下的所有序列中,与给定的DNA序列的LCS分别为\( [0,len(DNA)] \)的序列数量。

思路:
因为数据很小,我们可以考虑用状压做。
对于当前长度的一个最优状态,如果增加一个字符,它的下一个状态就需要加上当前状态的序列数量。
这是一个非常常见的计数DP。

但是已知当前状态,无法直接得出下一个状态,而这个就是我们需要嵌套在内的DP了。
我们枚举每一个状态,在枚举每一个字符,使其插入当前状态,再转移它的LCS,最后再统计一下就可以了。
而统计方法是如果当前位置的LCS与前一位置的LCS不同,则说明这个位置与LCS的DNA序列匹配。

虽然我说的很简洁,但是我当时也是想了好长时间……

AC Code

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
const int maxl = 16;
const int maxs = 1 << maxl;

char key[] = "ATCG";
size_t len;
int dp[2][maxs], ans[maxl];
int nexts[maxs][4];
int pre, cur = 1;
int cnt[maxl], lcs[maxl];

char str[maxl];

inline void add(int &a, int b) {
    a = a + b >= mod ? a + b - mod : a + b;
}

void init() {
    for (int sta = 0; sta < (1 << len); sta++) {
        for (int i = 1; i <= len; i++)
            cnt[i] = cnt[i - 1] + (sta >> (i - 1) & 1);
        for (int k = 0; k < 4; k++) {
            for (int i = 1; i <= len; i++) {
                if (str[i] == key[k])
                    lcs[i] = cnt[i - 1] + 1;
                else
                    lcs[i] = max(lcs[i - 1], cnt[i]);
            }
            int &tmp = nexts[sta][k] = 0;
            for (int i = 1; i <= len; i++)
                tmp |= ((lcs[i] != lcs[i - 1]) << (i - 1));
        }
    }
    memset(dp, 0, sizeof dp);
    memset(ans, 0, sizeof ans);
}

int main() {
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%s %d", str + 1, &n);
        len = strlen(str + 1);
        init();
        dp[pre][0] = 1;
        for (int i = 0; i < n; i++) {
            memset(dp[cur], 0, sizeof dp[cur]);
            for (int sta = 0; sta < (1 << len); sta++)
                for (int j = 0; j < 4; j++)
                    add(dp[cur][nexts[sta][j]],dp[pre][sta]);
            cur ^= 1, pre ^= 1;
        }
        for (int sta = 0; sta < (1 << len); sta++)
            add(ans[__builtin_popcount(sta)], dp[pre][sta]);
        for (int i = 0; i <= len; i++)
            printf("%d\n", ans[i]);
    }
    return 0;
}
状压DP

HDU 4628 Pieces

Posted on

CLS的状压DP系列……
然而实际上也算是一道简单题,但是我并没有立刻写出来。
不知道为什么,每次我尝试这用已知最优状态去推其他状态都是错的……
然而用当前状态之前的状态来推当前状态却是对的。

顺便学习了一个,二进制子集的枚举方法。for ( int sta = state ; sta ; sta = (sta - 1) & state )
学了这么久状压居然连这个都知道真是醉了……

题意:
给你一个字符串,每次只能取走一个回文串,问最少取几次。

思路:
先预处理出所有状态是否为回文串,并使得 这个状态取值为 1 。
枚举每个状态,再枚举它的所有子集。
状态转移方程 为 dp[sta] = min(dp[sta], dp[sta ^ s] + dp[s] )

AC Code

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int maxn = 16;
const int inf = 0x3f3f3f3f;

char str[maxn];
int dp[1 << maxn];
int len;

void judge(int sta)
{
    if (dp[sta] != inf)
        return;
    int l = 0, r = len - 1;
    while (l < r) {
        while ((sta & (1 << l)) == 0 && l < len - 1)
            l++;
        while ((sta & (1 << r)) == 0 && r > 0)
            r--;
        if (str[l] != str[r]) {
            dp[sta] = inf + 1;
            return;
        }
        l++, r--;
    }
    dp[sta] = 1;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%s", str);
        len = strlen(str);
        int maxs = (1 << len) - 1;
        fill(dp, 0x3f), dp[0] = 0;
        range(sta, 1, maxs) each(j, len) judge(sta | (1 << j));
        range(sta, 1, maxs)
        {
            for (int s = sta; s; s = (s - 1) & sta)
                dp[sta] = min(dp[sta], dp[sta ^ s] + dp[s]);
        }
        printf("%d\n", dp[maxs]);
    }
    return 0;
}
树形DP

CodeForces 842 C Ilya And The Tree

Posted on

树上的选择性DP……
不是很懂其他人的做法,偶然间看到有人用ruby A了,我也就用ruby敲了一蛤
速度有点玄……

题意:
给你一棵树,每个节点都有权值,要你求每个节点到根节点所形成的树链 gcd。
其中每条树链都可以选择一个节点使得权值变为 0 。

思路:
感觉这就是裸题……
只不过就是把数组改成树上了而已。
用一个栈或者队列去遍历这棵树,对于每个节点是否变0都考虑一下就好了……

AC Code

#!/usr/bin/env ruby
# encoding: utf-8
n = gets.to_i
a = gets.split.map(&:to_i)
g = Array.new(n) {[]}

(n-1).times do
    u, v = gets.split.map(&:to_i)
    u, v = u-1, v-1
    g[u] << v
    g[v] << u
end

def GCD(a, b) return b == 0 ? a : GCD(b, a%b) end

dp = Array.new(n) { Array.new(2) { [] } }
dp[0] = [[a[0]], [0]]
par = [-1]*n

st = [0]
until st.empty?
    u = st.pop
    g[u].each do |v|
        next if v == par[u]
        par[v] = u
        st.push(v)
        dp[v][0] += dp[u][0].map{|x| GCD(x,a[v])}
        dp[v][1] += dp[u][0]
        dp[v][1] += dp[u][1].map{|x| GCD(x,a[v]) }
        2.times do |i|
            dp[v][i].uniq!
        end
    end
end

print a[0]
for u in 1...n do
    print " #{dp[u][1].max}"
end
简单DP

HDU 6143 Killer Names

Posted on

昨天的多校应该是团队合作最失败的一次……

一开始过题人数最多的那道题许颂嘉没去想,只能我自己上了,第一直觉就是DP,但这个状态转移真的想了我好久好久,但想出来后又觉得是非常显然的……

后来不知道什么时候许学姐来想这题了,估计是急了,也没跟我说,然后就是两个人单独想题的局面,还瞒着我敲了一发容斥……是的,一个队里两个人同时用两种算法在想同一题。这是团队赛最忌讳的。
也可以说是最愚蠢的。

之后敲完之后雨情学姐又给了我一个错误数据,先是打乱我的思路,然后debug了将近一个小时,发现数据错误之后,把最开始的代码交了一发就秒了……

不想多说什么,这场明明还有一道很简单的细心题,当时急了,没发现重点。和一道几乎是AC自动机入门题的题,没看。

我特么 心如刀割。

题意:
给你一个长度\( n\和字符数量\( m\),让你组成两个字符串,两个字符串两两不能有统一字符。

思路:
标程是容斥,我不会,这题提供DP解法。
令\( dp[ len ] [ num ] \) 表示长度为\( len \) 的字符串并且有\( num \)个字符的数量。
那么我现在只考虑一个字符串,它的长度固定为\( n\),我用 \( num\) 个字符去组成它,那么对于剩下可选的\( m - num \)个字符,任意组成另一个字符串。
这里所谓另一个字符串是可以直接求并且很好求的,就是\( ( m - num )^n \)。自己去体会啦
而\( dp [ len ] [ num ] \)可以通过如下转移方程求解。

$ dp[ len ] [ num ] = dp[ len - 1 ] [ num - 1 ] \times ( m - num + 1 ) + dp [ len - 1 ] [ num ] \times num $

略加思考就能体会到这个转移方程的正确性,这里就不说了。

AC Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
using namespace std;
typedef long long ll;

const int mod = 1e9+7;
const int maxn = 2e3+5;

int n,m;
ll dp[maxn][maxn];

ll fastPow(ll n,ll m)
{
    ll ans=1;
    while (m)
    {
        if (m&1)
            ans=ans*n%mod;
        n=n*n%mod;
        m>>=1;
    }
    return ans;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&n,&m);
        for(int len=1; len<=n; len++)
            dp[len][1]= m ;
        for(int num=2; num<=m; num++)
            dp[1][num] = 0;
        for(int len=2; len<=n; len++)
            for(int num=2; num<=m; num++)
                dp[len][num] = ((dp[len-1][num-1]*(m-num+1))%mod+(dp[len-1][num]*num)%mod)%mod;
        ll ans = 0;
        for(int num=1; num<m; num++)
            ans = (ans+dp[n][num] * fastPow(m-num,n))%mod;
        printf("%lld\n",ans);
    }
    return 0;
}