水题笔记_ Noip2005T2 过河 [DP×离散化]

诶嘿嘿嘿嘿嘿嘿嘿嘿嘿嘿嘿嘿(此人已疯)
最近打算刷DP去惹…但是窝的DP怕是还停留在小学生水平…什么都不会诶嘿嘿嘿嘿嘿….

懵逼的 题目

传送至 Vijos

扯淡的 题解

先打了个30分的…然后wa了…诶嘿嘿嘿嘿嘿嘿嘿嘿
然后发现没有考虑跳过去的情况
然后又wa了…诶嘿嘿嘿嘿嘿嘿嘿嘿
然后发现没有加min…
写完啦30分 看看10^9…
诶这个石头只有100个啊…诶差这么大肯定离散化啊
如果两个石头之间的距离大于t(跳一次无法到达) 就把他缩短(反正题目不管你跳几步) 但是缩成多少呢… 反正只要保证不出错就好了…讨论里有说 t (t - 1) 的… 正当窝想的时候…Refun突然对窝说学长说这个题可以把距离 % 一个2520…因为这是1到10的最小公倍数…结果窝就错失了思考这个题核心部分的机会(珍爱生命远离Refun)…

沙茶的 代码

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 <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define MAXSL (252000 + 5) // 最坏的可能是每两个石子间都是2520
#define MAXN (100 + 5)
#define TJM (2520) //诶嘿嘿嘿嘿嘿
using namespace std;
int l;
int n;
int s, t;
int stone[MAXN];
bool hs[MAXSL];
bool cmp(int, int);
int dp();
int main()
{
memset(hs, false, sizeof(hs));
scanf("%d", &l);
scanf("%d%d%d", &s, &t, &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &stone[i]);
}
sort(stone + 1, stone + n + 1);
stone[0] = 0;
int srx = 0;
for (int i = 1; i <= n; i++)
{
if (stone[i] - stone[i - 1] > t)
{
srx += (stone[i] - stone[i - 1]) % TJM;
}
else
{
srx += stone[i] - stone[i - 1];
}
hs[srx] = true;
}
l = srx;
printf("%d", dp());
return 0;
}
int dp()// 从三十分那个地方复制过来就好啦~ 所以谁说考场先打暴力没用呢?
{
int f[MAXSL];
memset(f, 0x7f, sizeof(f));
f[0] = 0;
for(int i = 0; i <= l; i++)
{
for (int j = s; j <= t; j++)
{
if (hs[i + j])
{
f[i + j] = min(f[i + j], f[i] + 1);
}
else
{
f[i + j] = min(f[i + j], f[i]);
}
}
}
for (int i = 0; i <= t; i++)
{
f[l] = min(f[l], f[l + i]);
}
return f[l];
}

By 有点疯的 Cansult