Celery's Blog

0%

LeetCode-Day53

发表于 更新于 Valine：

HDU 4489 The King’s Ups and Downs

题意：给你n个身高高低不同的士兵。问你把他们按照波浪状排列(高低高或低高低)有多少方法数。

思路：dp[i][1]表示前i个人最后第i个人以降序结尾的方法总数，dp[i][0]表示前i个人中最后第i个人以升序结尾的方法总数。

假设第i个人是最高的，那么将第i个人放在j+1的位置，那么前面j个人中最后一个人必须是降序结尾的，然后前i-1个人中的候i-j-1个人则不一定。但是一定是按矮—高—矮…的顺序的。由于奇数个人的时候，结尾的顺序与起始是一样的，即开始为矮，结束也是矮，若为偶数则相反。

因此有：

dp[i][0] = sum(C(j, i)*dp[j][1]*dp[i-j-1][0])

dp[i][1] = sum(C(j, i)*dp[j][1]*dp[i-j-1][1])

因此：综上dp[i][(i-j-1)&1] = sum(C(j, i)*dp[j][1]*dp[i-j-1][(i-j-1)&1])

还有一点需要补充：

Cab=Ca−1b−1+Ca−1bC_a^b = C_{a-1}^{b-1} +C_{a-1}^{b}

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 23;
int n, setN, num;
ll dp[MAXN][2];
ll C[MAXN][MAXN];
void solve() {
    for(int i = 0; i <= 20; i++)  {
        C[i][0] = 1;
        for(int j = 1; j <= i; j++) {
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }
    dp[0][0] = dp[0][1] = 1;
    dp[1][0] = dp[1][1] = 1;
    dp[2][0] = dp[2][1] = 1;
    for(int i = 3; i <= 20; i++) {
        for(int j = 0; j < i; j++) {
            dp[i][(i-j-1)&1] += dp[j][1] * dp[i-j-1][(i-j-1)&1] * C[i-1][j];
        }
    }
}

int main() {
    scanf("%d", &n);
    memset(dp, 0, sizeof(dp));
    solve();
    for(int i = 0; i < n; i++) {
        scanf("%d%d", &setN, &num);
        if(num == 1) {
            printf("%d 1\n", setN);
        } else {
            printf("%d %lld\n", setN, dp[num][0] + dp[num][1]);
        }
    }
}

POJ 1745 Divisibility

题意：给你n个数，经过加减的操作，看能不能整除K。

思路：

dp[i][j]表示前i个数是否可以通过加减操作，然后整除K的余数为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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 10003;
const int MAXM = 103;
int arr[MAXN];
int dp[2][MAXM];
int n, k;

void solve() {
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    int now = 0, pre = 1;
    for(int i = 1; i <= n; i++) {
        // 滚动数组
        now ^= 1;
        pre ^= 1;
        memset(f[now], 0, sizeof(f[now]));
        for(int j = 0; j <= k; j++) {
            dp[now][(j + arr[i]) % k] |= dp[pre][j];
            dp[now][(j - arr[i] + k) % k] |= dp[pre][j];
        }
    }
    if(dp[n][0]) {
        printf("Divisible\n");
    } else {
        printf("Not divisible\n");
    }
}

int main() {
    while(scanf("%d%d", &n, &k) != EOF) {
        for(int i = 1; i <= n; i++) {
            scanf("%d", &arr[i]);
            // arr[i] %= k;
            (arr[i] += k) %= k;
        }
        for(int i = 1; i <= n; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
        solve();
    }
}

PS：这里需要注意的就是负数的处理，可以先取余数，然后加上K之后再%K，就能保证一定在0~K-1之间了！！

POJ 2355 Railway tickets

题目大意：X为距离 ， 当0<X<=L1， 票价为C1。 L1<X<=L2 ，票价为C2。L2<X<=L3，票价为C3。给每段车站时间的距离，求某两个车站之间的总票价的最小值。

思路：

dp[i]表示从start到i的最小票价

dp[i] = min(dp[i], dp[j] + (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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
typedef long long ll;
using namespace std;
const int MAXN = 10010;
int C1, C2, C3, L1, L2, L3;
ll dp[MAXN];
int way[MAXN];
int n, start, end;
void solve() {
    memset(dp, 0, sizeof(dp));
    for(int i = start + 1; i <= end; i++) {
        dp[i] = INT_MAX;
        bool flag = false;
        for(int j = i - 1; !flag && j >= 0; j--) {
            int dist = way[i] - way[j];
            if(dist <= L1) {
                dp[i] = min(dp[i], dp[j] + C1);
            } else if(dist <= L2) {
                dp[i] = min(dp[i], dp[j] + C2);
            } else if(dist <= L3) {
                dp[i] = min(dp[i], dp[j] + C3);
            } else {
                flag = true;
            }
        }
    }
    printf("%d\n", dp[end]);
}

int main() {
    scanf("%d%d%d%d%d%d", &L1, &L2, &L3, &C1, &C2, &C3);
    scanf("%d", &n);
    scanf("%d%d", &start, &end);
    if(start > end) {
        swap(start, end);
    }
    for(int i = 2; i <= n; i++) {
        scanf("%d", &way[i]);
    }
    solve();
}

这里需要注意的就是：

求解dp[i]的时候，只需要利用dp[i]-dp[j]<L3范围内的j即可，然后按照dp[i]-dp[j]的范围来确定买哪个区间的票即可，即如果距离小于L1，就没必要买L2的票，因此最多只有四种情况，超出L3范围即可跳出循环，求解i+1了。