Skip to content

12204: 【原2204】欢总的袜子

题目

题目描述

author: 李霖 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/2204

诗经有云:

瞻彼淇奥,绿竹猗猗。有匪君子,如切如磋,如琢如磨。瑟兮僴兮,赫兮咺兮,有匪君子,终不可谖兮。

瞻彼淇奥,绿竹青青。有匪君子,充耳琇莹,会弁如星。瑟兮僴兮,赫兮咺兮,有匪君子,终不可谖兮。

瞻彼淇奥,绿竹如箦。有匪君子,如金如锡,如圭如璧。宽兮绰兮,猗重较兮,善戏谑兮,不为虐兮。

彼竹青青,恰如君子。君子谓谁?学长欢总也。大家都知道,欢总好男人!IT男中的战斗男!欢总不仅写程序写得棒,而且洗袜子洗得也非常专业!雨季过了,又到了洗袜子的时节……欢总不洗则已,一洗洗了好多双!

阳光明媚的午后,欢总终于洗完了袜子,他开始把袜子挂到晾衣架上。欢总的晾衣架可以看做一个杠杆,上面固定着一些钩子,袜子只能挂在钩子上。挂好的袜子要符合杠杆原理,这样的晾衣架才能平衡。每个钩子的位置用数轴上的坐标表示,杠杆支点在坐标原点。欢总想知道究竟有多少种袜子的挂法。

Input Format

第1行:两个整数m, n, 表示晾衣架上有m个钩子,一共有n只袜子。

第2行:一共m个整数,表示每个钩子的坐标x。

第3行:一共n个整数,表示每只袜子的重量w。

Output Format

一共一行,这一行只有一个数字,表示一共有多少种袜子的挂法。

Hint

所有的袜子都要挂到上去,且每个钩子可以挂多只袜子;

2 <= m <= 20;

2 <= n <= 20;

对于每个钩子的坐标x,-15 <= x <= 15;

对于每个袜子的重量w,1 <= w <= 25;

Sample Input

2 5
-15 -11
24 4 21 19 10

Sample Output

0

yyong119's solution

#include <cstdio>
#define MAX_N 25
#define MAX_M 25
#define OFFSET 7510
#define MAX_LEN 30
#define max(x, y) ((x) > (y) ? (x) : (y))
using namespace std;
int n, m;
int pos[MAX_M], w[MAX_N];
struct LONGINT {
    int len;
    int num[MAX_LEN];
    LONGINT(): len(1) {}
    LONGINT operator+=(const LONGINT &p) {
        int length_m = max(len, p.len);
        // add p to this
        for (register int i = 0; i < length_m; ++i) {
            num[i] += p.num[i];
            if (num[i] > 9) {
                ++num[i + 1];
                num[i] -= 10;
            }
        }
        len = (num[length_m] ? length_m + 1 : length_m);
        return *this;
    }
} f[MAX_N][OFFSET << 1];
// long long f[MAX_N][OFFSET << 1];
int main() {
    scanf("%d %d", &m, &n);
    for (register int i = 0; i < m; ++i) scanf("%d", &pos[i]);
    for (register int i = 1; i <= n; ++i) scanf("%d", &w[i]);
    f[0][OFFSET].num[0] = 1;
    // dp
    for (register int i = 1; i <= n; ++i)
        for (register int j = 0; j < (OFFSET << 1); ++j)
            for (register int k = 0; k < m; ++k) {
                // put the i-th socks to k-th hook
                int prev_state = j - w[i] * pos[k];
                if (prev_state >= 0 && prev_state < (OFFSET << 1))
                    f[i][j] += f[i - 1][prev_state];
            }
    // output
    for (register int i = f[n][OFFSET].len - 1; i > -1; --i)
        printf("%d", f[n][OFFSET].num[i]);
    return 0;
}