洛谷 过河

题号:1052
参考题解:
https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1052
作者: CoolTeam 更新时间: 2015-08-11 18:26
作者: shutdown 更新时间: 2013-07-30 20:20
作者: VengefulSpirit 更新时间: 2013-06-25 11:17
作者: sb123 更新时间: 2017-08-07 17:58

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
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<queue>
#include<cstdlib>
#include<cstring>
#include<map>
using namespace std;
int f[20005];
int Mk[105],M[105];
//ifstream cin("in.txt");
//ofstream cout("out.txt");
int main(){
    ios::sync_with_stdio(false);
    int l, s, t, m,ans=0;
    cin >> l >> s >> t >> m;
    for (int i = 1; i <= m; i++){
        cin >> Mk[i];//存入M的临时数组
    }
    if (s == t){//当s==t时是特殊情况,只需判断为s/t倍数的点有无石子即可 ;参考CoolTeam。为啥用动态规划过不了,我也不知道
        for (int i = 1; i <= m; i++){
            if (Mk[i] % s == 0)ans++;
        }
        cout << ans;
        return 0;
    } //否则需要使用动态规划
    memset(f, 0x7f, sizeof(f));
    f[0] = 0;
    sort(Mk + 1, Mk + m + 1); //先给临时数组排个序
    for (int i = 1; i <= m; i++){
        if (Mk[i] - Mk[i - 1] >= 100)M[i] = M[i - 1] + 100; //如果两相邻石子之间距离大于100,就将他们之间的距离缩小到100 ;参考shutdown的结论,VengefulSpirit的证明过程
        else M[i] = M[i - 1] + Mk[i] - Mk[i - 1];
    }
    int M_cnt = 1;
    for (int i = 1; i <= M[m]+t; i++){ //比较容易的动态规划 ;参考sb123的动规转移方程
        for (int j = i-s; j >= max(i - t,0); j--){
            f[i] = min(f[j], f[i]);
        }
        if (M[M_cnt] == i){
            f[i]++;
            M_cnt++;
        }
    }
    ans = 10000;
    for (int i = M[m] + t-1; i >= M[m]; i--)ans = min(ans, f[i]);  //遍历从最后一个石子到最后一个石子+t-1的最短距离
    cout << ans;
}

20180805更新,表示缩点/离散化恶心死了,写了半天60,迫不得已看题解了。、
参考题解:https://www.luogu.org/blog/GXu/solution-p1052
https://peerless.blog.luogu.org/guo-he-xie-ti-bao-gao

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
#include<iostream>
#include<string>
#include<algorithm>
#include<functional>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int l;
int s, t, m;
int pos[105];
int d[105];
bool stone[400000];
int f[400000];
int main() {
    cin >> l >> s >> t >> m;
    for (int i = 1; i <= m; i++)cin >> pos[i];
    sort(pos + 1, pos + m + 1);
    for (int i = 1; i <= m; i++)d[i] = (pos[i] - pos[i - 1]) % 2520;
    for (int i = 1; i <= m; i++) {
        pos[i] = pos[i - 1] + d[i];
        stone[pos[i]] = true;
    }
    l = pos[m];
    for (int i = 1; i <= l + t; i++)f[i] = m;
    for (int i = 1; i <= l + t; i++) {
        for (int j = s; j <= t; j++) {
            if (i >= j)f[i] = min(f[i], f[i - j]);
            f[i] += stone[i];
        }
    }
    int ans = m;
    for (int i = l; i < l + t; i++)ans = min(ans, f[i]);
    cout << ans;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注