牛场围栏
fence.exe
【问题描述】
John计划为他的牛场建一个围栏，以限制奶牛们的活动。他有N种可以建造围栏的木料，长度分别是$l_1,l_2\dots l_N$，每种长度的木料无限。修建时，他将把所有选中的木料拼接在一起，因此围栏的长度就是他使用的木料长度之和。但是聪明的John很快发现很多长度都是不能由这些木料长度相加得到的，于是决定在必要的时候把这些木料砍掉一部分以后再使用。不过由于John比较节约，他给自己规定：任何一根木料最多只能削短M米。当然，每根木料削去的木料长度不需要都一样。不过由于测量工具太原始，John只能准确的削去整数米的木料，因此，如果他有两种长度分别是7和11的木料，每根最多只能砍掉1米，那么实际上就有4种可以使用的木料长度，分别是6, 7, 10, 11。
Clevow是John的牛场中的最聪明的奶牛，John请她来设计围栏。Clevow不愿意自己和同伴在游戏时受到围栏的限制，于是想刁难一下John，希望John的木料无论经过怎样的加工，长度之和都不可能得到她设计的围栏总长度。
不过Clevow知道，如果围栏的长度太小，John很快就能发现它是不能修建好的。因此她希望得到你的帮助，找出无法修建的最大围栏长度。
【输入文件】
输入文件的第一行包含两个整数N, M ($1\leqslant
N\leqslant100,\;0\leqslant M\leqslant3000$)，分别表示木料的种类和每根木料削去的最大值。以下各行每行一个整数$ l_i(1\leqslant l_i\leqslant3000)$,表示第i根木料的原始长度。
【输出文件】
输出文件仅一行，包含一个整数，表示不能修建的最大围栏长度。如果任何长度的围栏都可以修建或者这个最大值不存在，输出-1。
【输入输出样例】
fence.in
|
fence.out
|
2
1
7
11
|
15
|
【解析】
设S为所有可用长度的集合，T为所有已知长度的集合。由题意得：$card(S)\leqslant3000$，$max(S)\leqslant3000$，对于$\exists l\in S$，$\forall m\in T$使$0\leqslant m-l\leqslant M$。我们规定，可用表示成$ \sum_{l\in S,k\in N}kl$的数字称为“可表示的”。原题意转换为：求最大的不可表示的整数。这样转换题意后，本题似乎和NOIP 2017 Day 1 Problem 1类似。此题是否也是公式题呢？显然，冬令营不会考这么容易的题。
假设a可表示，则$a+kl,\;k\in Z,\;l\in S$ ($a+kl\geqslant0$)可表示。不妨设$i\leqslant min(S),\;l=min(S)$，所有可表示的数都可以写成$
i+kl,\;k\in\boldsymbol N\ast$的形式。记dp[i]表示最小的形如$ i+kl,\;k\in\boldsymbol N\ast$的可表示的数，$dp\lbrack
i\rbrack-l$一定不可被表示为$ i+kl,\;k\in\boldsymbol
N\ast$，这样通过遍历dp数组就可以求出答案。
上面一段讲得不是很清楚，我们举例说明：对于样例，S={6,7,10,11}，l=6，dp[]={0,7,14,21,10,11}。dp[]-l={-6,1,8,15,4,5}，其中最大的为15，所以答案是15。
现在我们考虑dp数组的求法。开始时遍历集合S，$dp\lbrack S_imod\;l\rbrack=S_i$，dp[0]=0，其他值初始化为INF。状态转移方程为：$dp\lbrack i\rbrack=min\{{dp\lbrack
j\rbrack+dp\lbrack(i-j)mod\;l\rbrack}\}$。
【参考程序】
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int INF = 0x3F3F3F3F;
void read(int &x)
{
x = 0; char ch = getchar(); bool f = 0;
while (ch>'9' || ch<'0') { if (ch == '-')f = 1; ch = getchar(); }
while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
if (f)x = -x;
}
bool
hashedS[3001];
int S[3000];
int dp[3000];
int main()
{
freopen("fence.in", "r", stdin);
freopen("fence.out", "w", stdout);
int n, m;
read(n); read(m);
for (int i = 0; i<n; i++)
{
int tmp;
read(tmp);
for (int j = max(tmp - m, 1); j <= tmp; j++)
{
hashedS[j]
= true;
}
}
int size = 0;
for (int i = 1; i <= 3000; i++)
{
if (hashedS[i])S[size++] = i;
}
memset(dp, 0x3F, sizeof(dp));
dp[0]
= 0;
for (int i = 0; i<size; i++)
{
dp[S[i]
% S[0]] = min(dp[S[i] % S[0]],
S[i]);
}
for (int i = 0; i<S[0]; i++)
{
for (int j = 0; j<S[0]; j++)
{
dp[i]
= min(dp[i], dp[j] + dp[(i - j +
S[0]) % S[0]]);
}
}
int ans = -1;
//dp[0]一定为0，枚举没有意义
for (int i = 1; i<S[0]; i++)
{
if (dp[i] == INF)continue;
ans
= max(ans, dp[i] - S[0]);
}
cout
<< ans << endl;
return 0;
}
没有评论:
发表评论