题解：P10489 [IOI1994] The Buses
Im_Klee
·
·
题解
前言
帮帮可莉吧！让可莉通过审核吧！
题意
给定 n 个数，求最少的等差数列个数，恰好覆盖 n 个数各一次。
至少 2 项，数值在 0 到 59 之间。
允许有重复的等差数列。
### 分析：
1. 考虑到 `DFS` 超时，而答案在 $17$ 以内，尝试 `IDDFS`。
2. 预处理可能的等差数列，使得等差数列的每一项都在输入中出现。
3. 维护 `check` 函数检查第 $i$ 个等差数列的每一项是否都有出现，设找到 $cnt$ 条。
4. 将等差数列按项数从多到少排序，贪心选取，从而使得需要的公交路线最少。
5. 维护 $cnt_i$ 表示时间点 $i$ 出现的车的数量。
### 代码：
```cpp
#include<bits/stdc++.h>
using namespace std。
const int maxn = 305。
int cnt, dep, n, s[65]。
struct node
{
int x, d, num。
bool operator < (const node &a) const
{
return num > a.num。
}
}route[3600]。
bool check(int x, int d)
{
for(int i = x。 i < 60。 i += d)
if(s[i] == 0)
return false。
return true。
}
bool dfs(int cur, int k, int sum) //cur 层次，k线路， sum已经覆盖的车的数量
{
if(cur == dep)
return sum == n。
if(sum + (dep-cur) * route[k].num < n) //可行性剪枝
return false。
for(int i = k。 i <= cnt。 i++)
{
if(check(route[i].x, route[i].d) == true)
{
for(int j = route[i].x。 j < 60。 j += route[i].d)
s[j]--。
if(dfs(cur+1, i, sum + route[i].num) == true) //第i条路线还可以选!!
return true。
for(int j = route[i].x。 j < 60。 j += route[i].d) //回溯
s[j]++。
}
}
return false。
}
int main()
{
cin >> n。 //n车
for(int i = 1。 i <= n。 i++)
{
int x。
cin >> x。 //时间
s[x]++。 //计数器
}
for(int i = 0。 i < 60。 i++) //首项
{
for(int d = i + 1。 i + d < 60。 d++) //公差
{
if(check(i, d) == true) //找到可行的线路
{
cnt++。
route[cnt].x = i。 //首项
route[cnt].d = d。 //公差
route[cnt].num = (59-i) / d + 1。 //覆盖的公交车数量
}
}
}
sort(route + 1, route + cnt + 1)。 //按照覆盖的公交车数量从大到小排序
dep = 0。
while(dfs(0, 1, 0) == false) //当前的深度，选择线路编号， 覆盖的总公交
dep++。
cout << dep。
return 0。
}
//注意这组数据 0 4 4 8 8 12 12 ……
```