糯米

思路：

它的要求是，给你几个字母，用这些字母拼几个字典里面有的单词，所有单词加起来求最高得分。
转化一下，就是个01背包问题。
由于单词的长度很短很短了，只有3~7个字母，所以总状态数很少啦。数组开到 2048 就可以AC了。

后来又搜了一下别人的解题报告哦，发现有个哥们很牛逼。
他说：单词长度范围在3--7内。所以可能的词组 只能是 3+3 或 3+4

#include <stdio.h>

char key[] = {
    "qwertyuiop"
    "asdfghjkl"
    "zxcvbnm"
};
int score[] = {
    7, 6, 1, 2, 2, 5, 4, 1, 3, 5,
    2, 1, 4, 6, 5, 5, 7, 6, 3,
    7, 7, 4, 6, 5, 2, 5
};

int map[256], col[256], idx[256], mul[8], tot[8], cnt, hash[2048], top;

int can_add(int a, int b)
{
    int i, ia, ib;

    for (i = 1; i < cnt; i++) {
        ia = (a / mul[i - 1]) % tot[i];
        ib = (b / mul[i - 1]) % tot[i];
        if (ia + ib >= tot[i])
            return 0;
    }

    return 1;
}

int main()
{
    int i, val, sum[256], sc;
    char str[16];

    freopen("e:\\test\\in.txt", "r", stdin);

    for (i = 0; i < 26; i++)
        map[key[i]] = score[i];
    
    scanf("%s", str);
    for (i = 0; str[i]; i++)
        col[str[i]]++;

    cnt = 1;
    for (i = 'a'; i <= 'z'; i++)
        if (col[i]) {
            idx[i] = cnt;
            mul[cnt] = tot[cnt] = col[i] + 1;
            cnt++;
        }

    mul[0] = 1;
    for (i = 1; i < cnt; i++)
        mul[i] *= mul[i - 1];
    top = mul[cnt - 1];
    hash[0] = 1;

    while (scanf("%s", str), str[0] != '.') {
        for (i = 'a'; i <= 'z'; i++)
            sum[i] = 0;
        sc = 0;
        val = 0;
        for (i = 0; str[i]; i++) {
            sum[str[i]]++;
            if (sum[str[i]] > col[str[i]])
                break;
            sc += map[str[i]];
            val += mul[idx[str[i]] - 1];
        }
        if (str[i])
            continue;
        for (i = top; i >= 0; i--) {
            if (!hash[i])
                continue;
            if (can_add(i, val) && hash[i + val] < hash[i] + sc)
                hash[i + val] = hash[i] + sc;
        }
    }

    sc = 0;
    for (i = top; i >= 0; i--)
        if (hash[i] > sc)
            sc = hash[i];
    printf("%d\n", sc - 1);

    return 0;
}

#include <stdio.h>
#include <string.h>

#define MAX_LEN 256

int tbl[MAX_LEN];
char *str = "abbbbbbb";
char *ptn = "bb";
char spc[MAX_LEN];

int main()
{
    int i, j;

    memset(spc, ' ', sizeof(spc));

    tbl[0] = 0;
    for (i = 1; ptn[i]; i++) {
        for (j = tbl[i - 1]; j && ptn[j] != ptn[i]; j = tbl[j]);
        if (ptn[j] == ptn[i])
            j++;
        tbl[i] = j;
    }
    printf("table:\n");
    for (i = 0; ptn[i]; i++) 
        printf("  %c", ptn[i]);
    printf("\n");
    for (i = 0; ptn[i]; i++)
        printf("%3d", tbl[i]);
    printf("\n");

    j = 0;
    for (i = 0; str[i]; ) {
        printf("\nmatching #%d\n", i);
        printf("%s\n", str);
        fwrite(spc, 1, i - j, stdout);
        printf("%s\n", ptn);
        fwrite(spc, 1, i, stdout);
        printf("^\n");
    
        if (str[i] == ptn[j]) {
            i++;
            j++;
            printf("ok\n");
        } else {
            if (j) 
                j = tbl[j - 1];
            else
                i++;
            printf("jumped to %d\n", j);
        }
        if (!ptn[j])
            printf("matched at %d\n", i);
    }

    return 0;
}

输出：
table:
  b  b
  0  1

matching #0
abbbbbbb
bb
^
jumped to 0

matching #1
abbbbbbb
 bb
 ^
ok

matching #2
abbbbbbb
 bb
  ^
ok
matched at 3

matching #3
abbbbbbb
 bb
   ^
jumped to 1

matching #3
abbbbbbb
  bb
   ^
ok
matched at 4

matching #4
abbbbbbb
  bb
    ^
jumped to 1

matching #4
abbbbbbb
   bb
    ^
ok
matched at 5

matching #5
abbbbbbb
   bb
     ^
jumped to 1

matching #5
abbbbbbb
    bb
     ^
ok
matched at 6

matching #6
abbbbbbb
    bb
      ^
jumped to 1

matching #6
abbbbbbb
     bb
      ^
ok
matched at 7

matching #7
abbbbbbb
     bb
       ^
jumped to 1

matching #7
abbbbbbb
      bb
       ^
ok
matched at 8

思路：

差分约束是个很神奇的东西，能将下面这种类型的不等式约束问题：
d[1] - d[2] <= a
d[4] - d[7] <= b
...
求 d[x] 的最大/小值
转化为最短路径的问题，真吗的太牛逼了。
原理呢，就是一个图求出单源最短路径之后。
两点之间的关系必然是满足 d[u] + w[u,v] >= d[v] 的，没法再松弛了。

#include <stdio.h>

#define MAX_DIS 1000000032
#define MAX_N 1024
#define MAX_EDGES 65536

struct edge_node {
    int i, w;
    struct edge_node *next;
};

int N, ML, MD;
struct edge_node edges[MAX_EDGES], *map[MAX_N];
int edges_cnt;
int D[MAX_N], queue[MAX_N], head, tail, vis[MAX_N], tm, cnt[MAX_N];

inline void add_edge(int a, int b, int w)
{
    struct edge_node *e = &edges[edges_cnt++];

    e->i = b;
    e->w = w;
    e->next = map[a];
    map[a] = e;
}

inline int push(int i, int d)
{
    if (d >= D[i])
        return 0;
    D[i] = d;
    if (vis[i] == tm)
        return 0;
    vis[i] = tm;
    cnt[i]++;
    if (cnt[i] >= N)
        return 1;
    queue[tail++] = i;
    tail &= MAX_N - 1;
    return 0;
}

inline int spfa()
{
    int i;
    struct edge_node *e;

    for (i = 1; i <= N; i++) 
        D[i] = MAX_DIS;
    tm++;
    head = tail = 0;
    push(1, 0);
    while (head != tail) {
        i = queue[head++];
        head &= MAX_N - 1;
        vis[i] = 0;
        for (e = map[i]; e; e = e->next) 
            if (push(e->i, D[i] + e->w))
                return 1;
    }

    return 0;
}

int main()
{
    int a, b, w, i;

    freopen("e:\\test\\in.txt", "r", stdin);

    scanf("%d%d%d", &N, &ML, &MD);
    while (ML--) {
        scanf("%d%d%d", &a, &b, &w);
        add_edge(a, b, w);
    }
    while (MD--) {
        scanf("%d%d%d", &a, &b, &w);
        add_edge(b, a, -w);
    }
    for (i = 2; i <= N; i++)
        add_edge(i, i - 1, 0);

    if (spfa())
        a = -1;
    else
        a = (D[N] == MAX_DIS) ? -2 : D[N];
    printf("%d\n", a);

    return 0;
}

思路：

这题完全不懂，看了这份大牛的解题报告
http://hi.baidu.com/winterlegend/blog/item/2411981e8fd0ed6bf724e45e.html
发现吗的太牛逼了！

首先二分图匹配，正常情况下，都是单个单个的点这样匹配、
但是像这道题，右边的点一个可以匹配好几个左边的点。也是用匈牙利算法，不过要做少少修改。

枚举答案的时候，有两种方法：
一个是移动区间的方法。复杂度O(B)。注意，只移动区间右边的时候不用重新匹配，只需要接着上次没匹配完的继续匹配就行了
一个是二分法。复杂度 O(B lgB)
由于数据的问题，这两种方法时间相差无几。在 16ms 和 32ms 之间。

#include <stdio.h>

struct barn {
    int link[1024], cnt, vis, cap;
};
struct cow {
    int rank[32];
};

struct barn barns[32];
struct cow cows[1024];
int start, end, last_pos;
int N, B, tm;

int dfs(int c)
{
    int i, j;
    struct barn *b;

    for (i = start; i <= end; i++) {
        b = &barns[cows[c].rank[i]];
        if (b->vis == tm)
            continue;
        b->vis = tm;
        if (b->cnt < b->cap) {
            b->link[b->cnt++] = c;
            return 1;
        }
        for (j = 0; j < b->cap; j++)
            if (dfs(b->link[j])) {
                b->link[j] = c;
                return 1;
            }
    }
    return 0;
}

inline void init()
{
    int i;

    for (i = 1; i <= B; i++)
        barns[i].cnt = 0;
    last_pos = 1;
}

inline int match()
{
    int i, j;

    for (i = last_pos; i <= N; i++) {
        tm++;
        if (!dfs(i))
            break;
    }
    last_pos = i;
    return i > N;
}

int main()
{
    int i, j, ans;

    freopen("e:\\test\\in.txt", "r", stdin);

    scanf("%d%d", &N, &B);
    for (i = 1; i <= N; i++)
        for (j = 1; j <= B; j++)
            scanf("%d", &cows[i].rank[j]);
    for (i = 1; i <= B; i++)
        scanf("%d", &barns[i].cap);
    
#if 0
    // O(B)
    ans = B;
    start = end = 1;
    while (start <= B && end <= B) {
        init();
        while (end <= B && !match())
            end++;
        if (end - start + 1 < ans)
            ans = end - start + 1;
        start++;
    }
#else
    // O(B*lgB)
    int l, r, m;

    l = 1;
    r = B;
    while (l <= r) {
        m = (l + r) / 2;
        for (start = 1; start <= B - m + 1; start++) {
            end = start + m - 1;
            init();
            if (match())
                break;
        }
        if (start == B - m + 2) {
            // failed
            l = m + 1;
        } else 
            r = m - 1;
    }
    ans = r + 1;
#endif

    printf("%d\n", ans);

    return 0;
}