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

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;
}