Celery's Blog

0%

挑战程序设计竞赛-day6

发表于 Valine：

POJ 3616 Milking Time

大意：贝茜是一个勤劳的牛。事实上，她如此专注于最大化她的生产力，于是她决定安排下一个N（1≤N≤1,000,000）小时（方便地标记为0…N-1），以便她生产尽可能多的牛奶。

农民约翰有一个M（1≤M≤1,000）可能重叠的间隔列表，他可以在那里进行挤奶。每个区间我有一个起始小时（0≤starting_houri≤N），一个结束小时（starting_houri <ending_houri≤N），以及相应的效率（1≤efficiencyi≤1,000,000），表示他可以从中获取多少加仑的牛奶。贝西在那段时间。 Farmer John分别在开始时间和结束时间开始时开始和停止挤奶。在挤奶时，Bessie必须在整个间隔内挤奶。

尽管贝茜有其局限性。在任何间隔期间挤奶后，她必须休息R（1≤R≤N）小时才能再次开始挤奶。鉴于Farmer Johns的间隔清单，确定Bessie在N小时内可以产生的最大牛奶量。

提醒：休息时间，如：第3小时结束工作，休息2小时，第5小时就可以开始工作。

思路：

首先按照结束时间进行排序，设res[i]表示工作到第i时刻，最大的收益

如果此时i为其中一个结束时间，则res[i] = max(res[i], res[i - 1], res[max(0, start - j)] + eff)

表示i时刻的最大收益来源是上一个时刻的工资，或之前计算出来的工资（因为给的数据可能在同一时间结束的有好几组，所以需要和原来的值进行比较），或者是开始工作前r小时的收益加上这次工作的收益。

如果不是结束时间，则收益和前一时刻是一样的，因为这个时间段要不就是没工作，要不就是还没工作完，都是没有收益的

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int M = 1010;
const int N = 1000010;
int n, m, r;
struct node {
    int start; 
    int end;
    int eff;
};

bool cmp(const node &a, const node &b) {
    if(a.end == b.end) {
        return a.start < b.start;
    }
    return a.end < b.end;
}

node cows[M];
int res[N];
void solve() {
    int j = 0;
    int i = 1;
    while(i <= n && j < m) {
        if(i < cows[j].end) {
            res[i] = max(res[i], res[i - 1]);
        } else {
            res[i] = max(res[i], max(res[i - 1], res[max(0, cows[j].start - r)] + cows[j].eff));
            j++;
            continue;
        }
        i++;
    }
    printf("%d\n", max(res[i], res[n]));
}

int main() {
    while(scanf("%d%d%d", &n, &m, &r) != EOF) {
        for(int i = 0; i < m; i++) {
            scanf("%d%d%d", &cows[i].start, &cows[i].end, &cows[i].eff);
        }
        sort(cows, cows + m, cmp);
        memset(res, 0, sizeof(res));
        solve();
    }
}

POJ 3280 Cheapest Palindrome

大意：给定一个字符串S，字符串S的长度为M(M≤2000)，字符串S所含有的字符的种类的数量为N(N≤26)，然后给定这N种字符Add与Delete的代价，求将S变为回文串的最小代价和。

思路：

改天打算看看关于回文串的一些解题思路（先记下来，免得忘记

设dp[i][j]表示，S[i]-S[j]变成回文串最少需要的代价，cost[i]表示删除或添加S[i]的较小代价。因为dp[i][j]表示的是将[i, j]范围内变成回文串，而处理两侧的一个字符，删除和添加是一样的性质，所以只需要求代价小的那个操作即可。

如果S[i] == S[j], 则dp[i][j] = dp[i + 1][j - 1]

否则dp[i][j] = min(dp[i + 1][j] + cost[S[i] - 'a'], dp[i][j - 1] + cost[S[j] - 'a'])

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 <cstdio>
#include <cstring>
#include <iostream>
const int INF = 99999999;
const int N = 2005;
using namespace std;
int cost[60];
int dp[N][N];
int main() {
    int n, m, x, y;
    char s[N], e;
    while(scanf("%d%d", &n, &m) != EOF) {
        scanf("%s", s);
        memset(cost, 0, sizeof(cost));
        for(int i = 0; i < n; i++) {
            cin >> e >> x >> y;
            cost[e - 'a'] = min(x, y);
        }
        memset(dp, 0, sizeof(dp));
        for(int k = 1; k < m; k++) {
            for(int i = 0, j = k; j < m; i++, j++) {
                dp[i][j] = INF;
                if(s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = min(dp[i][j], dp[i + 1][j] + cost[s[i] - 'a']);
                    dp[i][j] = min(dp[i][j], dp[i][j - 1] + cost[s[j] - 'a']);
                }
            }
        }
        printf("%d\n", dp[0][m - 1]);
        return 0;
    }
}

POJ 1743 Coins

大意：给定N种硬币，其中第 i 种硬币的面值为Ai,共有Ci个。从中选出若干个硬币，把面值相加，若结果为S，则称“面值S能被拼成”。求1~M之间能被拼成的面值有多少个。

dp[j]表示结果j能否被拼凑

sum[j]表示在使用价值为A[1]~A[i]的币拼凑结果为j - A[i]的时候，用的价值为A[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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 110;
const int M = 100010;
int n, m;
int A[N], C[N];
bool dp[M]; // 为1表示可以凑成
int sum[M];
// int f[M], g[M];
void solve() {
    memset(dp, 0, sizeof(dp));
    int res = 0;
    dp[0] = 1;
    for(int i = 0; i < n; i++) {
        memset(sum, 0, sizeof(sum));
        for(int j = A[i]; j <= m; j++) {
            if(!dp[j] && dp[j - A[i]] && sum[j - A[i]] < C[i]) {
                dp[j] = 1;
                sum[j] = sum[j - A[i]] + 1;
                res++;
            }
        }
    }
    printf("%d\n", res);
}

int main() {
    while(scanf("%d%d", &n, &m) && n) {
        for(int i = 0; i < n; i++) {
            scanf("%d", &A[i]);
        }
        for(int i = 0; i < n; i++) {
            scanf("%d", &C[i]);
        }
        solve();
    }
}

POJ 3046 Ant Counting

大意：给出T种元素，每个元素个数为tot[i],询问从所有元素中挑出k个组成的不同集合数目sum[k],k∈[S,B] ,ans=SUM{sum[k] | S<=k<=B}

为了防止超出内存，使用了滚动数组。

d[i][j]表示用i种元素，组成j的方案数

dp[i][j] = sum(dp[i - 1][k]), k从max(0, j - num[i])到j

即用i种类元素组成j实际上就是用i - 1种元素组成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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int T = 100010;
const int N = 1010;
const int MAXN = 1000000;
int t, a, s, b;

int  num[N];
int dp[2][T];
// s和b表示一个区间
void solve() {
    dp[0][0] = 1;
    for(int i = 1; i <= t; i++) {
        for(int j = 0; j <= a; j++) {
            int sum = 0;
            for(int k = max(0, j - num[i]); k <= j; k++) {
                sum = (sum + dp[(i - 1) % 2][k]) % MAXN;
            }
            dp[i % 2][j] = sum;
        }
    }
    int total = 0;
    for(int i = s; i <= b; i++) {
        total = (total + dp[t % 2][i]) % MAXN;
    }
    printf("%d\n", total);
}

int main() {
    while(scanf("%d%d%d%d", &t, &a, &s, &b) != EOF) {
        memset(num, 0, sizeof(num));
        for(int i = 0; i < a; i++) {
            int n;
            scanf("%d", &n);
            num[n]++;
        }
        memset(dp, 0, sizeof(dp));
        solve();
    }
}

POJ 3181 Dollar Dayz

这是一个划分数问题，即求一个数N能被1-T的数划分的方案数

dp[i][j]表示用i~i的数拼凑成j的方案数

则dp[i][j] = dp[i - 1][j] + dp[i][j - i]

即要不就是用前1 ~ i - 1的数拼凑j，或者用1 ~ i的数拼凑j - i

注意到这个二维其实可以化简成一维的问题，因为在计算dp[i][j]只用到了上一行的第j位和已经计算过的当前行的j - 1位，所以该式子也可以写成dp[j] = dp[j] + dp[j - i]

但是这里需要注意的就是，这个值有可能过大，并且用long long都不能表示，但是使用高精度又太花费时间，因此这里采用dp1来表示高位，dp2来表示低位

所以dp[j] = dp1[j] * mod + dp1[j] + dp2[j - i] * mod + dp2[j - i]

dp2[j] = (dp1[j] + dp2[j - i]) % mod

dp1[j] = dp1[j] + dp2[j - i] + (dp1[j] + dp2[j - i]) / mod

因为计算之后dp1[j]会发生变化，所以必须dp2[j]先计算

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL dp1[1005], dp2[1005], mod;
int N, K;

int main() {
    scanf("%d%d", &N, &K);
    mod = 1;
    for(int i = 1; i <= 18; i++) {
        mod *= 10;
    }
    dp2[0] = 1LL;
    for(int i = 1; i <= K; i++) {
        for(int j = i; j <= N; j++) {
            dp1[j] += dp1[j - i] + (dp2[j] + dp2[j - i]) / mod;
            dp2[j] = (dp2[j] + dp2[j - i]) % mod;
        }
    }
    if(dp1[N]) {
        cout << dp1[N];
    }
    cout << dp2[N];
    return 0;
}

明天写一下今晚npy教的Hash~~