1. HDU1024 Max Sum Plus Plus

题目链接

题意：长度为 $n(1\le n\le10^6)$ 的序列 $a_1,a_2,\cdots,a_n$，定义片段和 $sum(i,j)=a_i+\cdots+a_j$，求 $m(m\gt0)$ 个不相交片段和的最大值。

  定义状态 $dp_{i,j}$ 表示取 $i$ 个片段以 $a_j$ 结尾的最大值，则

$$dp_{i,j}=\max(dp_{i,j-1},\max_{i-1\le k\le j-1}{dp_{i-1,k}})+a_j$$

  上面式子中，前面将 $a_j$ 放入第 $i$ 部分，后面将 $a_j$ 单独做第 $i$ 部分。$n$ 最大为 $10^6$，用滚动数组优化，可直接缓存记录所需最大值。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e6 + 5;

int a[N], dp[N], mx[N];
int m, n, ans;

int main() 
{
    while(~scanf("%d%d", &m, &n)) {
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        dp[0] = 0;
        memset(mx, 0, sizeof(mx));
        for (int i = 1; i <= m; ++i) {
            ans = -INF;
            for (int j = i; j <= n; ++j) {
                dp[j] = max(dp[j-1], mx[j-1]) + a[j];
                mx[j-1] = ans;
                ans = max(ans, dp[j]);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

2. HDU1029 Ignatius and the Princess IV

题目链接

题意：给出奇数 $n(1\le n\le10^6-1)$ 个数字，找出出现至少 $(n+1)/2$ 次的数。

  可以直接用 map 不会 T，也可以利用出现次数抵消最后留下的即答案。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f;

int n, cnt, ans;

int main() 
{
    while (~scanf("%d", &n)) {
        int x;
        cnt = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &x);
            if (!cnt) {
                ans = x;
                cnt++;
            }
            else {
                if (ans == x) cnt++;
                else cnt--;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

3. HDU1069 Monkey and Banana

题目链接

题意：给出 $n(1\le n\le30)$ 种长方体，长方体的数量无限，将它们堆成塔，要求上面的方块比下面的长和宽都要小，求塔的最大高度。

  每种方块最多有 3 种不同的底面和高度（相同的也算），将每种方块视为 3 个不同的方块，将方块按照长宽递减的顺序排序，最后找最大高度类似 LIS，$dp[i]$ 表示以第 i 块方块为顶的塔的最大高度，那么状态转移方程：

$$dp[i]=\max(dp[i],dp[j]+a[i].z)\quad(j\lt i,a[j].x\gt a[i].x\ and\ a[j].y\gt a[i].y)$$

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 100;

struct rec {
    int x, y, z;
    bool operator < (const rec &b) const {
        if (x != b.x) return x > b.x;
        return y > b.y;
    }
}a[N];

int n, cas;
int dp[N];

int main() 
{
    while (scanf("%d", &n), n) {
        int x, y, z;
        for (int i = 1; i <= n; ++i) {
            scanf("%d%d%d", &x, &y, &z);
            if (x < y) swap(x, y);
            if (x < z) swap(x, z);
            if (y < z) swap(y, z);
            a[3*i-2] = {x, y, z};
            a[3*i-1] = {y, z, x};
            a[3*i] = {x, z, y};
        }
        n *= 3;
        sort(a + 1, a + n + 1);
        for (int i = 1; i <= n; ++i) dp[i] = a[i].z;
        int ans = dp[1];
        for (int i = 2; i <= n; ++i) {
            // printf("x, y, z: %d %d %d\n", a[i].x, a[i].y, a[i].z);
            for (int j = 1; j < i; ++j) {
                if (a[j].x > a[i].x && a[j].y > a[i].y) dp[i] = max(dp[i], dp[j] + a[i].z);
            }
            ans = max(ans, dp[i]);
        }
        printf("Case %d: maximum height = %d\n", ++cas, ans);
    }
    return 0;
}

4. HDU1074 Doing Homework

题目链接

题意：有 $n(1\le n\le15)$ 个作业，每个作业有截至时间和完成所需时间，每个作业超过截止时间一天扣一分，求完成所有作业的最少扣分。

   $n$ 很小，首先想到状压 dp，$dp[st]$ 表示状态 $st$ 时的最少扣分，$st$ 二进制表示中第 $i$ 位为 1 表示第 $i$ 种作业已完成，所求即 $dp[2^n-1]$，输出字典序最小的方案，则倒序枚举 $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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 16;

int t, n;
int dp[1<<15], pre[1<<15], time[1<<15];
int bin[N], d[N], c[N];
string s[N];

void print(int id) {
    if (!id) return;
    print(id ^ bin[pre[id]]);
    cout << s[pre[id]] << '\n';
}

int main() 
{
    bin[0] = 1; for (int i = 1; i <= 15; ++i) bin[i] = bin[i-1] << 1;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            cin >> s[i]; scanf("%d%d", &d[i], &c[i]);
        }
        memset(pre, 0, sizeof(pre));
        for (int st = 1; st < bin[n]; ++st) {
            dp[st] = INF;
            for (int i = n - 1; i >= 0; --i) {
                int tmp = bin[i];
                if (!(st & tmp)) continue;
                int reduce = time[st-tmp] + c[i] - d[i];
                if (reduce < 0) reduce = 0;
                if (dp[st] > dp[st-tmp] + reduce) {
                    dp[st] = dp[st-tmp] + reduce;
                    time[st] = time[st-tmp] + c[i];
                    pre[st] = i;
                }
            }
        }
        printf("%d\n", dp[bin[n]-1]);
        print(bin[n] - 1);
    }
    return 0;
}

5. HDU1087 Super Jumping! Jumping! Jumping!

题目链接

题意：求和最大的递增子序列。

  类似 LIS，$dp[i]$ 表示以 $i$ 结尾的结果，将 $O(n^2)$ 的状态转移方程中的 +1 修改为 +a[i] 即可，因为是和最大而不是序列最长，不能用 $O(n\log{n})$ 二分的方法改。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1005;

int n;
int a[N], dp[N];

int main() 
{
    while (scanf("%d", &n), n) {
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            dp[i] = a[i];
            for (int j = 1; j < i; ++j)
                if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + a[i]);
            ans = max(ans, dp[i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

6. HDU1114 Piggy-Bank

题目链接

题意：给出存钱罐的初始质量和装满硬币的质量，$n(1\le n\le500)$ 种硬币和每种硬币的价值和重量，求装满硬币后存钱罐可能的最小价值，如果重量无法达到，输出 This is impossible.。

  硬币数量无限制，是完全背包问题，采用正向循环时，对应每种物品可以使用无限次。

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 505, M = 1e4 + 5;

int t, a, b, n;
int p[N], w[N];
int f[M];

int main() 
{
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d", &a, &b, &n);
        for (int i = 1; i <= n; ++i) scanf("%d%d", &p[i], &w[i]);
        memset(f, 0x3f, sizeof(f));
        f[0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = w[i]; j <= b - a; ++j)
                f[j] = min(f[j], f[j-w[i]] + p[i]);
        }
        if (f[b-a] == INF) puts("This is impossible.");
        else printf("The minimum amount of money in the piggy-bank is %d.\n", f[b-a]);
    }
    return 0;
}

7. HDU1176 免费馅饼

题目链接

题意：在数轴 $[0,11]$ 上，人站在 5，天上掉馅饼，人的移动速度为 1，给出馅饼掉落位置和时间，求最多能接到几个馅饼。

  数塔问题，类似于 HDU2084，$dp[i][j]$ 表示第 i 秒第 j 个位置得到馅饼的最大值，状态转移方程：

$$dp[i][j]=dp[i][j]+\max(dp[i+1][j],\max(dp[i+1][j-1],dp[i+1][j+1]))$$

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e5 + 5;

int n;
int dp[N][15];

int main() 
{
    while (scanf("%d", &n), n) {
        int x, y, t = 0;
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; ++i) {
            scanf("%d%d", &x, &y);
            dp[y][x+1]++;
            t = max(t, y);
        }
        for (int i = t - 1; i >= 0; --i) {
            for (int j = 11; j >= 1; --j) {
                dp[i][j] += max(dp[i+1][j], max(dp[i+1][j-1],dp[i+1][j+1]));
            }
        }
        printf("%d\n", dp[0][6]);
    }
    return 0;
}

8. HDU1260 Tickets

题目链接

题意：n 个人买票，给出 n 个人单独买票发花费的时间，n-1 个数表示一个人和前一个人一起买票花费的时间，求最早什么时间卖完票(08:00:00开始)。

  $dp[i]$ 表示前 $i$ 个人需要的时间，$a[i]$ 表示第 $i$ 人单独买票时间，$b[i]$ 表示第 $i$ 个人和第 $i-1$ 个人买票需要的时间，则 $dp[i]=\min(dp[i-1]+a[i],dp[i-2]+b[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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 2005;

int t, n;
int a[N], b[N], dp[N];

int main() 
{
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        for (int i = 2; i <= n; ++i) scanf("%d", &b[i]);
        dp[1] = a[1];
        for (int i = 2; i <= n; ++i)
            dp[i] = min(dp[i-1] + a[i], dp[i-2] + b[i]);
        int h, m, s;
        h = (dp[n] / 3600 + 8) % 24;
        m = dp[n] / 60 % 60;
        s = dp[n] % 60;
        if (h > 12) printf("%02d:%02d:%02d pm\n", h - 12, m, s);
        else printf("%02d:%02d:%02d am\n", h, m, s);
    }
    return 0;
}

9. HDU1257 最少拦截系统

题目链接

题意：一种导弹拦截系统，第一发可以任意高度，拦截的每一发炮弹不能超过前一发炮弹，给出导弹个数和每个的高度，求最少需要的导弹拦截系统套数。

  考虑什么时候需要增加拦截系统，当后面的高度比前面大时，可以转化为求最长递增子序列的问题。

$O(n^2)$

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1005;

int n;
int a[N], f[N];

int main() 
{
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            f[i] = 1;
            for (int j = 1; j < i; ++j) {
                if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
            }
            ans = max(ans, f[i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

$O(n\log{n})$

 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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1005;

int n;
int a[N], f[N];

int main() 
{
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            f[i] = INF;
        }
        for (int i = 1; i <= n; ++i) {
            *lower_bound(f + 1, f + n + 1, a[i]) = a[i];
        }
        printf("%lld\n", lower_bound(f + 1, f + n + 1, INF) - f - 1);
    }
    return 0;
}

10. HDU1160 FatMouse’s Speed

题目链接

题意：。