这两道题都是从我开始接触tyvj的时候就看过的，可是一直没去写，今天终于。。。

P1064 - 新三国争霸

描述 Description
PP 特别喜欢玩即时战略类游戏，但他觉得那些游戏都有美中不足的地方。灾害总不降临道路，而只降临城市，而且道路不能被占领，没有保护粮草的真实性。于是他就研发了《新三国争霸》。
在这款游戏中，加入灾害对道路的影响（也就是一旦道路W[i，j]受到了灾害的影响，那么在一定时间内，这条路将不能通过）和道路的占领权（对于一条道路W[i，j]，至少需要K[i，j]个士兵才能守住）。
PP可真是高手，不一会，就攻下了N-1座城市，加上原来的就有N座城市了，但他忽略了一点……那就是防守同样重要，不过现在还来的及。因为才打完仗所以很多城市都需要建设，PP估算了一下，大概需要T天。他现在无暇分身进攻了，只好在这T天内好好的搞建设了。所以他秒要派士兵占领一些道路，以确保任何两个城市之间都有路（不然敌人就要分而攻之了，是很危险的）。士兵可不是白干活的，每个士兵每天都要吃掉V的军粮。因为有灾害，所以方案可能有变化（每改变一次就需要K的军粮，初始方案也需要K的军粮）。
因为游戏是PP编的，所以他知道什么时候有灾害。PP可是一个很节约的人，他希望这T天在道路的防守上花最少的军粮。
N<=300，M<=5000 ，T<=50；

输入格式 InputFormat
第一行有5个整数N，M，T，V，K。N表示有城市数，M表示道路数，T表示需要修养的天数，V表示每个士兵每天吃掉的军粮数，K表示修改一次花掉的军粮数。
以下M行，每行3个数A，B，C。表示A与B有一条路（路是双向的）需要C个士兵才能守住。
第M+2行是一个数P，表示有P个灾害。
以下P行，每行4个数，X，Y，T1，T2。表示X到Y的这条路，在T1到T2这几天都会受灾害。

输出格式 OutputFormat
T天在道路的防守上花费最少的军粮。

样例输入 SampleInput [复制数据]
3 3 5 10 30
1 2 1
2 3 2
1 3 4
1
1 3 2 5
样例输出 SampleOutput [复制数据]
180
个人感觉一道不错的动态规划题吧，一直不敢下手写，写完真是心旷神怡啊～～
设F[i]表示前i天的最少花费，则有
F[i] = min(F[i], F[j-1] + mt(i-j+1)v+k)
其中，mt表示第j天到第i天的最少花费，也就是在第j天到第i天可通行的道路求一遍最小生成树，一开始我是认为必须在第j天到第i天均不能通行的才不用排兵去收，不过事实好像是只要这期间道路遭遇灾害就可以不用派兵把守了。还是说是我没读懂题意

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int MM = 5050;
const int INF = 1000000000;

struct edge{
    int x, y, w;
    bool operator < (const edge & a) const {
        return w < a.w;
    }
} e[MM];

int n, m, t, v, k, p;
bool can[MM], road[MM][MM];
int f[MM/10], fa[MM];

int getfa(int x) {
    return (fa[x] == x ? x : fa[x] = getfa(fa[x]));
}

int kruskal(int t1, int t2) {
    memset(can, true, sizeof(can));
    for (int i = 1; i <= m; i++)
        for (int j = t1; j <= t2; j++)
            if (!road[i][j]) {
                can[i] = false;
                break;
            }
    for (int i = 1; i <= m; i++)
        fa[i] = i;
    int ret = 0, cnt = 0;
    for (int i = 1; i <= m; i++)
        if (can[i]) {
            int f1 = getfa(e[i].x);
            int f2 = getfa(e[i].y);
            if (f1 != f2) {
                fa[f1] = f2;
                ret += e[i].w;
                cnt++;
                if (cnt == n-1)
                    return ret;
            }
        }
    return INF;
}

int main() {
    cin >> n >> m >> t >> v >> k;
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].w);
    sort(e+1, e+1+m);
    cin >> p;
    memset(road, true, sizeof(road));
    for (int i = 0; i < p; i++) {
        int x, y, t1, t2;
        scanf("%d%d%d%d", &x, &y,&t1, &t2);
        for (int j = 1; j <= m; j++)
            if (((e[j].x == x) && (e[j].y == y)) || ((e[j].x == y) && (e[j].y == x))) {
                for (int tt = t1; tt <= t2; tt++)
                    road[j][tt] = false;
            }
    }
    for (int i = 1; i <= t; i++)
        f[i] = INF;
    for (int i = 1; i <= t; i++)
        for (int j = 1; j <= i; j++)
            f[i] = min(f[i], f[j-1]+kruskal(j, i)*(i-j+1)*v+k);
    cout << f[t] << endl;
    return 0;
}

P1404 - [NOIP2010]引水入城

noip的题目，所以网上一堆题解，所以就贴一下自己的代码就好了

主要就是由一个证明说某蓄水池在最后一排城市可到达的是一个连续的区间，然后就可以从第一排开始dfs求出对应区间的左右边界，然后就是一个最小区间覆盖吧，然后数据好像之后500，DP一下就行，然后好像关于最小区间覆盖的话是有一个贪心的解法。以后再想想看。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

const int MN = 510;

int n, m, root;
int dx[] = {0, -1, 0, 1};
int dy[] = {-1, 0, 1, 0};
int a[MN][MN];
int l[MN], r[MN], f[MN];
bool vis[MN][MN];
bool last[MN];

bool ck(int x, int y) {
    return (x > 0 && y > 0 && x <= n && y <= m);
}

void sc(int x, int y) {
    vis[x][y] = true;
    if (x == n) {
        last[y] = true;
        l[root] = min(l[root], y);
        r[root] = max(r[root], y);
    }
    for (int i = 0; i < 4; i++) {
        int tx = x + dx[i];
        int ty = y + dy[i];
        if (ck(tx, ty)) {
            if ((a[x][y] > a[tx][ty]) && (!vis[tx][ty]))
                sc(tx, ty);
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);
    memset(last, false, sizeof(last));
    for (int i = 0; i < MN; i++)
        l[i] = MN;
    for (int i = 1; i <= m; i++)
        if ((a[1][i] >= a[1][i-1]) && (a[1][i] >= a[1][i+1])) {
            memset(vis, false, sizeof(vis));
            root = i;
            sc(1, i);
    }
    int ans = 0;
    for (int i = 1; i <= m; i++)
        if (!last[i]) ans++;
    if (ans) {
        cout << 0 << endl << ans << endl;
        return 0;
    }
    f[0] = 0;
    for (int i = 1; i <= m; i++)
        f[i] = MN;
    for (int i = 1; i <= m; i++)
        for (int j = l[i]; j <= r[i]; j++)
            f[j] = min(f[j], f[l[i]-1] + 1);
    cout << 1 << endl;
    cout << f[m] << endl;
    return 0;
}