這題不懂做，一開始想了一個動態規劃的方法，復雜度很高。估計得幾百ms。
看status，覺得肯定有很低復雜度的方法。
然后看了 Discuss ，看到某位大牛說的貪心方法，頓時恍然大悟，嗎的實在太牛逼了。
這位大牛的解法如下：
想象自己是一個黑一日游的司機：
1.如果有乘客要上車，那么就讓他上，收錢！
2.如果超載了，把距目的地最遠的幾個乘客踢下去，退錢。
3.行駛到下一站

照著這個方法編碼，一開始速度很慢，后來改成用一個隊列來維護車上的乘客，速度就很快了，還飚上榜了。

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 10032
#define MAX_K 50032

struct slot_node {
    int end, cap;
    struct slot_node *next;
};
struct stat_node {
    int idx[MAX_N], cnt[MAX_N], head, tail, tot;
};
struct slot_node *start[2][MAX_N], slots[MAX_K*2];
struct stat_node stat[2];
int K, N, C, left, right, slots_cnt, ans;

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

inline void ins(int a, int b, int c, int d)
{
    struct slot_node *t;

    if (b > right)
        right = b;
    if (a < left)
        left = a;
    t = &slots[slots_cnt++];
    t->next = start[d][a];
    t->end = b;
    t->cap = c;
    start[d][a] = t;
}

inline void off(int d, int i)
{
    struct stat_node *t = &stat[d];

    if (t->head == t->tail || t->idx[t->head] != i) 
        return ;
    ans += t->cnt[t->head];
    t->tot -= t->cnt[t->head];
    t->head++;
}

inline void del(struct stat_node *t)
{
    int c;

    while (t->tot > C) {
        c = min(t->tot - C, t->cnt[t->tail - 1]);
        t->cnt[t->tail - 1] -= c;
        t->tot -= c;
        if (!t->cnt[t->tail - 1])
            t->tail--;
    }
}

inline void add(struct stat_node *t, int cap, int end)
{
    int i, j;

    t->tot += cap;

    for (i = t->tail - 1; i >= t->head; i--) {
        if (t->idx[i] == end) {
            t->cnt[i] += cap;
            return ;
        } else if (t->idx[i] < end)
            break;
    }
    i++;
    t->tail++;
    for (j = t->tail - 1; j > i; j--) {
        t->idx[j] = t->idx[j - 1];
        t->cnt[j] = t->cnt[j - 1];
    }
    t->idx[i] = end;
    t->cnt[i] = cap;
}

inline void on(int d, int i)
{
    struct slot_node *s;
    struct stat_node *t = &stat[d];

    for (s = start[d][i]; s; s = s->next) 
        add(t, s->cap, s->end);
    del(t);
}

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

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

    scanf("%d%d%d", &K, &N, &C);
    left = N;
    for (i = 0; i < K; i++) {
        scanf("%d%d%d", &a, &b, &c);
        if (a > b) 
            ins(N - a, N - b, c, 1);
        else
            ins(a, b, c, 0);
    }

    for (i = left; i <= right; i++) {
        off(0, i);
        off(1, i);
        on(0, i);
        on(1, i);
    }
    printf("%d\n", ans);

    return 0;
}

思路：

f[a][b] = { 種類數目為 a，螞蟻數目為 b 時候的方案總數 }
轉移：
f[a][b] = f[a - 1][0] + f[a - 1][1] + ... + f[a - 1][b]

時間 O(AT) 如果求 f[a][*] 只用一次循環的話
可以用循環數組

杯具：
把i看成j了，足足調了3個小時，注意，是不吃不喝，也沒有上廁所，沒有聽歌，沒有看優酷。。
是精神高度集中地浪費了3個小時！
與非主流之腦殘相比，有過之而無不及也。

#include <stdio.h>

#define P 1000000

int T, A, S, B, fam[1024], dp[2][1024*128], *cur, *pre;

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

int main()
{
    int i, j, cnt, end, sum;

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

    scanf("%d%d%d%d", &T, &A, &S, &B);
    for (i = 0; i < A; i++) {
        scanf("%d", &j);
        fam[j]++;
    }
    
    for (i = 0; i <= fam[1]; i++)
        dp[1][i] = 1;
    end = fam[1];

    for (i = 2; i <= T; i++) {
        cur = dp[i & 1];
        pre = dp[(i+1) & 1];
        cur[0] = pre[0];
        end += fam[i];
        for (j = 1; j <= end; j++) {
            cur[j] = cur[j - 1] + pre[j];
            if (j > fam[i])
                cur[j] -= pre[j - fam[i] - 1];
            cur[j] += P;
            cur[j] %= P;
        }
    }

    sum = 0;
    for (i = S; i <= B; i++) {
        sum += cur[i];
        sum %= P;
    }

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

    return 0;
}

首先考慮這個子問題：
從地圖上的某一點開始一直向右上方發展，一共能組成多少個以這個點的字母為開頭的單詞。
那么要把以這個點為左下角的矩形中的點全部都考察一遍。
假設這個點的字母為'N'，那就要看所有單詞組成的單詞樹里面，所有'N'節點孩子的字母，是否出現在這個矩形中。
如果有出現的話，則又是一個子問題了。
把所有這樣的子問題的和求出來，就是答案了。

再考慮一個細節：
'N'節點在單詞樹中可以出現很多次，因此每個'N'節點都是一個子問題。表示：
所有組成的單詞，第一個字母節點是'N'，余下的字母節點出現的'N'的子樹里。
動態規劃的時候，對于每個節點要處理一次，因為每個節點的孩子都不一樣。
在矩形中統計所有孩子對應的子問題的和。

關鍵是怎么存放子問題的答案：
我們需要找出矩形中跟指定孩子對應的點。如果把答案存放在地圖W*H的數組里面，那就比較麻煩，需要枚舉。
但是如果存放在單詞樹里面，就好很多。
如果我們從上往下掃描每一行，每一行從右到左掃描。那就只需要存放長度為W的一維數組了。

考慮一個細節：
對于地圖上的點'N'，要以什么樣的順序處理單詞樹的每個'N'。
按照單詞樹的位置，應該從上到下處理。

代碼寫出來，跑了100ms+，居然排到第9，然后換了gcc編譯，又排前了一點！
發現前面的人，除了第二名，估計算法都是一樣的。

思路：

就是一個最短路徑的問題。但是題目數據規模跟描述不符合。
數組要開大一些才能過。官方數據是描述是符合的，可能是管理員加了一些進去。

     摘要: 第一次寫這玩意，還真有點麻煩，出了點問題。然后看了一下別人的代碼，發現雙向邊，要分成兩個單向邊來插入。長見識了。而且費用的值有正有負，最好用SPFA來找最短路徑。思路：建立一個超級源點，跟點1連起來，容量為2。建立一個超級匯點，跟點N連起來，容量為2。其他的邊容量均為1。#include <stdio.h>#include <stdlib.h>#inc...  閱讀全文

思路：

留意到題目里面有一句話“All farms are connected one way or another to Farm 1.”。
這貌似說明圖一開始就是連通的。

二分答案，判斷依據是：
如果將大于某個長度的邊都去掉以后，圖就不連通了。
那這個長度相對答案來說，一定是大了。

思路：

每天要么以今天的價格買入，要么前面某天買了存在倉庫里。不存在一半是今天買的，一半是從倉庫拿的，這種情況。
因為如果這樣，肯定有一半具有更高的性價比，那就全部都改成更高性價比的方式就好了。。
所以，這題只需要保存一個當前的最大值，掃描一遍就能出結果了。瞬間就淪為一道水題了。還以為要大動作的呢。

思路：

深搜的時候，可以生成一棵樹。
深搜也就是深度遍歷這棵樹，把遍歷的路徑打印出來，就解決了一部分邊了，這部分邊都是經過兩次的，來一次去一次。
剩下的邊，就是遍歷的時候正在訪問的節點與已經訪問的節點之間的邊，很容易的判斷的。同樣把這部分路徑也打印出來。
后來看了 Discuss 才發現，這個東西叫做“歐拉回路”，又長見識了。

代碼