简单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;
}
简单DP

POJ 1661 Help Jimmy

Posted on

好题!!!!
这道题我整整想了一个晚上,怎么说呢,应该还是我从一开始就没想复杂,考虑得简单了,然后后面就写的很复杂了……

其实我在写到一半的时候就突然想到我的状态转移方程是错的,然而还是抱着poj数据弱的侥幸继续写下去……然后错误的地方越写越清晰……

题意:
一个90后都玩过的空间游戏吧,记得叫 是男人就下一百层 ,题意不是很好描述,可以自己去玩玩。

思路:
先说一下我最开始的想法,不想看的直接往下翻。
这道题我一看,诶,水题!我只要每次移动都保证当前层所花时间最少,类似记忆化搜索,一步一步推过去就能保证我的答案最优……

首先这个思路的确是对的,但却忽略了一个细节,从我以前走过的层到我当前层,有个位置上的关系。
就是说当我每次得到当前层时间最短的时候,我必须把落下的相应位置给确定下来,否则,若存在重复的最优时间,当前下落位置不同,会影响之后的时间。这是显然的。
而我要想补救我的思路,那我必须记录所有的位置,虽然这个位置数量不会超过2,但这实现起来就很烦。

正解:
其实正解是很简单的,我只要反向思考就可以了。就是记录当前层到底层的最短时间。考虑当前层到中间层再到底层,则中间层的起始位置必定是当前层的两边。若不存在中间层。则时间为高度,其实这个可以省略

所以只要考略每层的两边是否能到中间层即可。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <string>
#include <vector>

#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 inf = 0x3f3f3f3f;

struct node {
    int l, r, h;
    bool operator<(const node& a) const { return h < a.h; }
} s[1005];

int dp[1005][2];
int main()
{
    int n, t, x, y, limit;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d%d", &n, &x, &y, &limit);
        s[0].l = s[0].r = x, s[0].h = y;
        range(i, 1, n) scanf("%d%d%d", &s[i].l, &s[i].r, &s[i].h);
        sort(s, s + n + 1), fill(dp, 0);
        each(i, n + 1)
        {
            bool flag = false;
            reach(j, i) if (s[i].h - s[j].h <= limit && s[i].l >= s[j].l && s[i].l <= s[j].r)
            {
                dp[i][0] = min(dp[j][0] + s[i].l - s[j].l, dp[j][1] + s[j].r - s[i].l);
                flag = true;
                break;
            }
            if (!flag)
                dp[i][0] = s[i].h - s[0].h > limit ? inf : 0;
            flag = false;
            reach(j, i) if (s[i].h - s[j].h <= limit && s[i].r >= s[j].l && s[i].r <= s[j].r)
            {
                dp[i][1] = min(dp[j][0] + s[i].r - s[j].l, dp[j][1] + s[j].r - s[i].r);
                flag = true;
                break;
            }
            if (!flag)
                dp[i][1] = s[i].h - s[0].h > limit ? inf : 0;
        }
        printf("%d\n", min(dp[n][0], dp[n][1]) + y);
    }
    return 0;
}
简单DP

HDU 5074 Hatsune Miku

Posted on

老实说有点崩溃,一场训练赛,3道dp都没出,两道还是全世界都A了
毫无疑问,又落后一截……
实在不明白他们的dp为什么这么6……

题意:
给你一个序列 \( a_1 a_2 a_3 a_4 …… a_n \)
要你求相邻两个元素在矩阵中的数值和。
矩阵已给定,但是如果序列元素为负数,则可以为任意元素。

思路:
渐渐觉得dp就是暴力……
四种情况

ary[i-1] < 0 && ary[i] < 0dp[i][j] = max(dp[i][j], dp[i - 1][k] + mat[k][j])
ary[i-1] < 0 && ary[i] > 0dp[i][ary[i]] = max(dp[i][ary[i]], dp[i - 1][j] + mat[j][ary[i]])
ary[i-1] > 0 && ary[i] < 0dp[i][j] = max(dp[i][j], dp[i - 1][ary[i - 1]] + mat[ary[i - 1]][j])
ary[i-1] > 0 && ary[i] > 0dp[i][ary[i]] = dp[i - 1][ary[i - 1]] + mat[ary[i - 1]][ary[i]]

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#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;
const int maxn = 110;

int mat[maxn][maxn], dp[maxn][maxn];
int ary[maxn];

int main()
{
    int T, n, m;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        range(i, 1, m) range(j, 1, m) scanf("%d", &mat[i][j]);
        range(i, 1, n) scanf("%d", ary + i);
        fill(dp, 0);
        range(i, 2, n)
        {
            if (ary[i - 1] < 0)
                if (ary[i] < 0)
                    range(j, 1, m) range(k, 1, m) dp[i][j] = max(dp[i][j], dp[i - 1][k] + mat[k][j]);
                else
                    range(j, 1, m) dp[i][ary[i]] = max(dp[i][ary[i]], dp[i - 1][j] + mat[j][ary[i]]);
            else if (ary[i] < 0)
                range(j, 1, m) dp[i][j] = max(dp[i][j], dp[i - 1][ary[i - 1]] + mat[ary[i - 1]][j]);
            else
                dp[i][ary[i]] = dp[i - 1][ary[i - 1]] + mat[ary[i - 1]][ary[i]];
        }
        int ans = 0;
        range(i, 1, m) ans = max(ans, dp[n][i]);
        printf("%d\n", ans);
    }
    return 0;
}
简单DP

POJ 1692 Crossed Matchings

Posted on

坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑!!!!!!!!!

套着二分图外套的DP题!!!!
连续栽在这个类型的题上两次!!!!!!!!

一次是上次选拔赛的时候,那时候有两道题,一道是很明显的二分图,另一道稍微隐蔽一点,但是全都栽了,我以为,建了图我就是赢家,特么的根本建不出来!!!

上次就像写一篇来阐述一下某些二分图匹配的DP解法,无奈太懒了,结果今天就又栽在这里了……

题意:
给你一张二分图,要求点权相同的点才能相互匹配,而且每个匹配有且必须要有一个权值不同的匹配与其交叉,问最大匹配数量。

思路:
很容易想去匈牙利了有木有!!!但事实却是,dp求解。 思路如下:
假设我们要考虑的状态是第一行n位置,第二行m位置,且已知之前的所有最佳状态。考虑把,n,m交叉的匹配加入到匹配集合中。那么 如果两点的权值相同则不符合要求,否则,分别向前查找各自的匹配,再与这个状态之前的状态转移即可。

如果你还不懂,那你看一遍代码肯定能懂。

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;
const int inf = 0x3f3f3f3f;

const int maxn = 110;

int a[maxn], b[maxn];
int dp[maxn][maxn];

int main()
{
    int n, m, T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        range(i, 1, n) scanf("%d", a + i);
        range(i, 1, m) scanf("%d", b + i);
        fill(dp, 0);
        range(i, 2, n) range(j, 2, m)
        {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            if (a[i] != b[j]) {
                int k1 = i - 1, k2 = j - 1;
                while (k1 && a[k1] != b[j])
                    k1--;
                while (k2 && a[i] != b[k2])
                    k2--;
                if (k1 && k2)
                    dp[i][j] = max(dp[i][j], dp[k1 - 1][k2 - 1] + 2);
            }
        }
        printf("%d\n", dp[n][m]);
    }
    return 0;
}
BFS

CodeForces 295C Greg and Friends

Posted on

bfs + dp 好题。
真好,比赛的时候想不出来,看题解的时候感觉好复杂……
看完写的时候感觉非常流畅!

题意:
载人过岸,一艘船最大载重 k 已经给定。每个人的重量只会是50或者100。问最小的过岸次数与方案数。

思路:
老实说这个题目我可以看就知道是道搜索题,因为和那个什么东西(就是搜索入门的那个)来着非常像。
最重要的还是理清状态与思路。
以左岸50重人数,100重人数,船是否在左岸表示一个状态,对他进行 bfs ,只要满足船重量大于 0 并且小于等于最大 k,每次过岸花费 1 。第一个搜索到 最终状态的就是我们要求的结果。

而我们的方案数,只能通过dp来球,dp最讲求的就是状态,

转移方程如下:

如果是 左岸 -- > 右岸 anum表示 50重总人数 , bnum 表示 100重 总人数

\( dp[x][y][0] += dp[a][b][1] \times C_a^{a-x} \times C_b^{b-y} \)

否则

\( dp[x][y][1] += dp[a][b][0] \times C_{anum-a}^{x-a} \times C_{bnum-b}^{y-b} \)

写到中间的时候突然发现组合数求不来……尴尬……百度了一下,在数据较小的时候可以直接递推求

\( C_n^m = C_n^{m-1} + C_{n-1}^{m-1} \)

AC Code

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int maxn = 55;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;

int n, k;
int anum, bnum, maxa, maxb;
ll dp[maxn][maxn][2], c[maxn][maxn], dis[maxn][maxn][2];

struct status {
    int an;
    int bn;
    int isLeft;
    status() {}
    status(int _an, int _bn, int _isLeft)
        : an(_an)
        , bn(_bn)
        , isLeft(_isLeft)
    {
    }
};

queue<status> que;

int bfs()
{
    c[0][0] = 1;
    for (int i = 1; i <= 50; i++) {
        c[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    }
    maxa = anum > 0 ? k / anum : 0, maxb = bnum > 0 ? k / bnum : 0;
    que.push(status(anum, bnum, 1));
    dis[anum][bnum][1] = 0;
    dp[anum][bnum][1] = 1;
    status now, nxt;
    while (!que.empty()) {
        now = que.front();
        que.pop();
        if (!now.an && !now.bn && !now.isLeft)
            return dis[0][0][0];
        for (int i = 0; i <= maxb; i++)
            for (int j = i ? 0 : 1; j <= maxa; j++) {
                if (i * 100 + j * 50 > k)
                    break;
                if (now.isLeft) {
                    if (now.an - j < 0 || now.bn - i < 0)
                        continue;
                    nxt.an = now.an - j, nxt.bn = now.bn - i, nxt.isLeft = false;
                    (dp[nxt.an][nxt.bn][0] += dp[now.an][now.bn][1] * c[now.an][j] % mod * c[now.bn][i] % mod) %= mod;
                    if (!dis[nxt.an][nxt.bn][0]) {
                        dis[nxt.an][nxt.bn][0] = dis[now.an][now.bn][1] + 1;
                        que.push(nxt);
                    }
                } else {
                    if (now.an + j > anum || now.bn + i > bnum)
                        continue;
                    nxt.an = now.an + j, nxt.bn = now.bn + i, nxt.isLeft = true;
                    (dp[nxt.an][nxt.bn][1] += dp[now.an][now.bn][0] * c[anum - now.an][j] % mod * c[bnum - now.bn][i] % mod) %= mod;
                    if (!dis[nxt.an][nxt.bn][1]) {
                        dis[nxt.an][nxt.bn][1] = dis[now.an][now.bn][0] + 1;
                        que.push(nxt);
                    }
                }
            }
    }
    return -1;
}

int main()
{
    int weight;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &weight);
        if (weight == 50)
            anum++;
        else
            bnum++;
    }
    int step = bfs();
    if (step == -1) {
        puts("-1\n0");
    } else
        printf("%d\n%lld\n", step, dp[0][0][0]);
    return 0;
}