题目地址：洛谷：【P2592】[ZJOI2008]生日聚会 – 洛谷、BZOJ：Problem 1037. — [ZJOI2008]生日聚会Party

题目描述

今天是hidadz小朋友的生日，她邀请了许多朋友来参加她的生日party。 hidadz带着朋友们来到花园中，打算坐成一排玩游戏。为了游戏不至于无聊，就座的方案应满足如下条件：
对于任意连续的一段，男孩与女孩的数目之差不超过k。
很快，小朋友便找到了一种方案坐了下来开始游戏。hidadz的好朋友Susie发现，这样的就座方案其实是很多的，所以大家很快就找到了一种，那么到底有多少种呢？热爱数学的hidadz和她的朋友们开始思考这个问题……
假设参加party的人中共有n个男孩与m个女孩，你是否能解答Susie和hidadz的疑问呢？由于这个数目可能很多，他们只想知道这个数目除以12345678的余数。

题意简述

有$n$个男孩$m$个女孩，要求把这些排成一排，使得每一个连续区间内男女孩的数量之差的绝对值不超过$k$，求排列的方案数，对$12345678$取模。

输入输出格式

输入格式：
输入文件party.in仅包含一行共3个整数，分别为男孩数目n, 女孩数目m, 常数k。

输出格式：
输出文件party.out应包含一行，为题中要求的答案。

输入输出样例

输入样例#1：

1 2 1

输出样例#1：

1

说明

对于30%的数据，n , m ≤ 20；
对于100%的数据, n , m ≤ 150，k ≤ 20。

题解

大力DP。
设计状态$dp[i][j][x][y]$表示排列前$i$个人，其中$j$个男孩，$i-j$个女孩，以$i$结尾的任意一段男孩-女孩的最大值$x$，以$i$结尾的任意一段女孩-男孩的最大值$y$的方案数，若$x, y$出现负数情况视为$0$处理，大力枚举第$i$个是男孩还是女孩转移即可。
复杂度$O(n^2k^2)$。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MO = 12345678;

int n, m, k, dp[305][155][25][25];

int main() {
    n = readint(); m = readint(); k = readint();
    dp[0][0][0][0] = 1;
    for(int i = 0; i < n + m; i++) {
        for(int j = 0; j <= n; j++) {
            for(int x = 0; x <= k; x++) {
                for(int y = 0; y <= k; y++) {
                    if(!dp[i][j][x][y]) continue;
                    if(j + 1 <= n && x + 1 <= k) {
                        dp[i + 1][j + 1][x + 1][std::max(y - 1, 0)] += dp[i][j][x][y];
                        dp[i + 1][j + 1][x + 1][std::max(y - 1, 0)] %= MO;
                    }
                    if(i + 1 - j <= m && y + 1 <= k) {
                        dp[i + 1][j][std::max(x - 1, 0)][y + 1] += dp[i][j][x][y];
                        dp[i + 1][j][std::max(x - 1, 0)][y + 1] %= MO;
                    }
                }
            }
        }
    }
    int ans = 0;
    for(int i = 0; i <= k; i++) {
        for(int j = 0; j <= k; j++) {
            ans = (ans + dp[n + m][n][i][j]) % MO;
        }
    }
    printf("%d", ans);
    return 0;
}

题目地址：洛谷：【P4026】[SHOI2008]循环的债务 – 洛谷、BZOJ：Problem 1021. — [SHOI2008]Debt 循环的债务

题目描述

Alice、Bob和Cynthia总是为他们之间混乱的债务而烦恼，终于有一天，他们决定坐下来一起解决这个问题。不过，鉴别钞票的真伪是一件很麻烦的事情，于是他们决定要在清还债务的时候尽可能少的交换现金。
比如说，Alice欠Bob 10元，而Cynthia和他俩互不相欠。现在假设Alice只有一张50元，Bob有3张10元和10张1元，Cynthia有3张20元。一种比较直接的做法是：Alice将50元交给Bob，而Bob将他身上的钱找给Alice，这样一共就会有14张钞票被交换。但这不是最好的做法，最好的做法是：Alice把50块给Cynthia，Cynthia再把两张20给Alice，另一张20给Bob，而Bob把一张10块给C，此时只有5张钞票被交换过。
没过多久他们就发现这是一个很棘手的问题，于是他们找到了精通数学的你为他们解决这个难题。

题意简述

有三个人，有六种可以用来支付的钞票，面值分别为$100, 50, 20, 10, 5, 1$，他们互相有一些欠钱关系，1欠2的钱为$x_1$，2欠3的钱为$x_2$，3欠1的钱为$x_3$，现在给你每个人拥有的6种钞票数量，求最少的钞票交换次数，使得互相欠的钱可以被还清。

输入输出格式

输入格式：
输入的第一行包括三个整数：x1、x2、x3（-1,000≤x1，x2，x3≤1,000），其中x1代表Alice欠Bob的钱（如果x1是负数，说明Bob欠了Alice的钱），x2代表Bob欠Cynthia的钱（如果x2是负数，说明Cynthia欠了Bob的钱），x3代表Cynthia欠Alice的钱（如果x3是负数，说明Alice欠了Cynthia的钱）
接下来有三行，每行包括6个自然数：
a100，a50，a20，a10，a5，a1
b100，b50，b20，b10，b5，b1
c100，c50，c20，c10，c5，c1
a100表示Alice拥有的100元钞票张数，b50表示Bob拥有的50元钞票张数，以此类推。
另外，我们保证有a10+a5+a1≤30，b10+b5+b1≤30，c10+c5+c1≤30，而且三人总共拥有的钞票面值总额不会超过1,000。

输出格式：
如果债务可以还清，则输出需要交换钞票的最少张数；如果不能还清，则输出“impossible”（注意单词全部小写，输出到文件时不要加引号）。

输入输出样例

输入样例#1：

10 0 0
0 1 0 0 0 0
0 0 0 3 0 10
0 0 3 0 0 0

输出样例#1：

5

输入样例#2：

-10 -10 -10
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

输出样例#2：

0

说明

对于100%的数据，x1、x2、x3 ≤ |1,000|。

题解

数据范围非常动态规划。我们设计这样的状态，$dp[i][s1][s2]$表示只考虑前$i$种钞票，第一个人当前所持金额为$s1$，第二个为$s2$，第三个人可以通过总金额减去前两个人的金额算出。我们枚举前两个人第$i$种钞票在交换后有多少，然后计算每个人的该种钞票数量差值绝对值之和的一半，即为从原来状态到当前状态第$i$种钞票的最小交换次数。最后判断互不相欠的情况下是否有人金额为负数以及该情况是否可达就好。
不过似乎，BZOJ的1s时限这种方法过不去。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline int min(int a, int b) {
    return a < b ? a : b;
}

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 1005, INF = 0x3f3f3f3f;
const int par[] = {0, 100, 50, 20, 10, 5, 1};

int x1, x2, x3, a[4][7], dp[2][MAXN][MAXN], cnt[7], sum[4];

int main() {
    x1 = readint(); x2 = readint(); x3 = readint();
    for(register int i = 1; i <= 3; i++) {
        for(register int j = 1; j <= 6; j++) {
            a[i][j] = readint();
            cnt[j] += a[i][j];
            sum[i] += a[i][j] * par[j];
        }
    }
    int l1 = sum[1] + x3 - x1, l2 = sum[2] + x1 - x2, l3 = sum[3] + x2 - x3;
    if(l1 < 0 || l2 < 0 || l3 < 0) {
        puts("impossible"); return 0;
    }
    sum[0] = sum[1] + sum[2] + sum[3];
    for(register int i = 0; i <= sum[0]; i++) {
        memset(dp[0][i], 0x3f, sizeof(int) * (sum[0] + 2));
    }
    dp[0][sum[1]][sum[2]] = 0;
    int now = 1, s3, c3, ns1, ns2, ns3;
    for(register int i = 1; i <= 6; i++) {
        for(register int i = 0; i <= sum[0]; i++) {
            memset(dp[now][i], 0x3f, sizeof(int) * (sum[0] + 2));
        }
        for(register int s1 = 0; s1 <= sum[0]; s1++) {
            for(register int s2 = 0; s1 + s2 <= sum[0]; s2++) {
                s3 = sum[0] - s1 - s2;
                if(dp[now ^ 1][s1][s2] >= INF) continue;
                dp[now][s1][s2] = min(dp[now][s1][s2], dp[now ^ 1][s1][s2]);
                for(register int c1 = 0; c1 <= cnt[i]; c1++) {
                    for(register int c2 = 0; c1 + c2 <= cnt[i]; c2++) {
                        c3 = cnt[i] - c1 - c2;
                        ns1 = s1 + (c1 - a[1][i]) * par[i];
                        ns2 = s2 + (c2 - a[2][i]) * par[i];
                        ns3 = s3 + (c3 - a[3][i]) * par[i];
                        if(ns1 < 0 || ns2 < 0 || ns3 < 0) continue;
                        dp[now][ns1][ns2] = min(dp[now][ns1][ns2],
                            dp[now ^ 1][s1][s2] + (abs(c1 - a[1][i]) + abs(c2 - a[2][i]) 
                            + abs(c3 - a[3][i])) / 2);
                    }
                }
            }
        }
        now ^= 1;
    }
    if(dp[now ^ 1][l1][l2] >= INF) {
        puts("impossible");
    } else {
        printf("%d", dp[now ^ 1][l1][l2]);
    }
    return 0;
}