主题：有关USACO1.3的第2个问题求助！
MK
[专家分：110] 发布于 2005-04-15 19:43:00
请问谁知道有关USACO1.3第二题牛棚修理怎么做啊？
附：
输入：牛棚个数（<=200,>0);几个牛棚有牛；板子数；（不限长度）
一下每行输入一个有牛的牛棚号数；
输出：用的最少长度（用完所有板子，板子盖多少个牛棚都行，但有牛的地方都必须盖住，求最小值）。
一牛场的牛棚一面墙都被吹掉了，现有M块木板，不限长度，现有牛的牛棚都必须盖住，板子书小于有牛的牛棚数，求最小值。
回复列表 （共18个回复）
沙发
huga3 [专家分：50] 发布于 2005-04-16 22:24:00
用动态规划吧：g(i,k)=min{g(j,k-1)+i-j}，j=1,...,i-1
g(i,k)表示盖1-i牛棚用k块板最小值。
板凳
faintzw [专家分：2660] 发布于 2005-04-17 07:23:00
不要误导……这个显然是贪心
3 楼
smallboat [专家分：60] 发布于 2005-04-17 09:23:00
已经好久没做Usaco的题了，搞计算机竞赛的？？
这是我的账号，已经做到4.1了，你可以参考一下它提供的算法
还有，搞竞赛最好去大榕树信息学竞赛论坛。
UserName: smallbo1
Password: xt4e6ts
4 楼
MK [专家分：110] 发布于 2005-04-17 20:01:00
确实是贪心，我需要完整程序！
5 楼
MK [专家分：110] 发布于 2005-04-17 20:04:00
能讲清楚动态规划吗？
6 楼
MK [专家分：110] 发布于 2005-04-17 20:09:00
我需要PASCAL语言的算法，C语言的看不懂！
7 楼
huga3 [专家分：50] 发布于 2005-04-17 21:13:00
1.3的题，好像贪心是能过。好早以前做的了，记不太清了，若真“误导”，那就抱歉罗……^o^
8 楼
huga3 [专家分：50] 发布于 2005-04-17 21:32:00
{动态规划算法：}
fillchar(g,sizeof(g),0);
a:=有牛的编号最靠前的牛棚号；
b:=有牛的编号最靠后的牛棚号；
for i:=a to b do
if 第i个牛棚有牛 then g[i,1]:=i-a+1
else g[i,1]:=g[i-1,1]; {初始化，只盖一块板}
for k:=2 to m(板个数) do
for i:=a to b do
if 第i个牛棚无牛 then g[i,k]:=g[i-1,k]
else begin
g[i,k]:=i-a+1;
for j:=a to i-1 do
if g[j,k-1]+(i-j) < g[i,k] then g[i,k]:=g[j,k-1]+(i-j);
end;
g[b,m]为所求。
{思路就是这样吧，我没原题和测试数据，所以没编程试过。:P 高手们多多指教！谢~~}
9 楼
裴晚辰 [专家分：0] 发布于 2005-05-28 07:24:00
[em2][em1][em1][em10][em10][em10][em10][em10][em10][em10][size=4][color=800000]哇,好深奥[/color]
10 楼
微风习习 [专家分：0] 发布于 2005-08-01 16:51:00
有谁能提供完整程序呢~~~~~最好不是动态规划的~~~~~~谢了~~~~~~无限期待~~~~~~~~~
我来回复
您所在位置：