过河
【过河】http://codevs.cn/problem/1105/
http://www.acmicpc.sdnu.edu.cn/problem/show/1087
这题看了两天，第一天没看懂路径压缩，第二天差不多做出来了，还有点小瑕疵。
#include
#include
#include
#include
#include
using namespace std;
int main()
{
intaa[10050] = { 0 };
int bb[10050] = { 0 };
int f[10050] = { 0 };
int l, s, t, m;
cin >> l >> s >> t >> m;
for (int i = 1;
i <= m;
i++)
{
scanf_s("%d", &bb[i]);
}
sort(bb + 1, bb + m + 1);
int k = 0;
for (int i = 1;
i < m + 1;
i++)
{
if (bb[i] - bb[i - 1]>s*t)
k = k + s*t;
else
k = k + bb[i] - bb[i - 1];
aa[k]++;
}
for (int i = 1;
i <= k + t;
i++)
{
int mintemp = 999999;
for (int j = i - t;
j <= i - s;
j++)
{
if (j >= 0)
mintemp = min(mintemp, f[j]);
}
f[i] = mintemp + aa[i];
}
int daan = 99999;
for (int i = k;
i < k + t + 1;
i++)
{
daan = min(daan, f[i]);
}
if (s == t)
{
daan = 0;
for (int i = 1;
i < m + 1;
i++)
{
if (bb[i] % s == 0)
daan++;
}
}
cout << daan << endl;
system("pause");
return 0;
} 推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长