讨论 / 第四个点为什么过不去?
B-L-A-C-K 2008-10-27 02:00:00
点我顶贴 收藏 删除
01背包求最小值嘛,第四个点输出-1,好像是什么特殊情况啊?大家来看看

(vijos p1428 跟这题基本一样,同样的算法也有一个点过不了啊)

program p202;

var f:array[0..21,0..79] of longint;

ss,bb,s,b,c,i,j,k,n:longint;

begin

read(ss,bb,n);

for i:=0 to ss do

for j:=0 to bb do f[i,j]:=-1;

f[0,0]:=0;

for i:=1 to n do

begin

read(s,b,c);

for j:=ss downto s do

for k:=bb downto b do

if f[j-s,k-b]>=0 then

if (f[j,k]=-1)or(f[j-s,k-b]+c<f[j,k]) then f[j,k]:=f[j-s,k-b]+c;

for j:=1 to s do

for k:=1 to b do

if (f[j,k]=-1)or(f[j,k]>c) then f[j,k]:=c

end;

write(f[ss,bb])

end.

#1 飞雪天涯@2008-10-24 08:38:00
回复 删除
(我的微软拼音终于克服了病毒!)

用装箱问题的解法去解(DP),此题非常简单,但注意下标越界问题

另外,其实火炬手可以扛大于t的氧气,大于a的氮气(阴险啊!)

此下是我的code(ac):

/*

Show Problem

题目:奥运火炬登珠峰 问题编号:202 My Flag:Unsubmited

题目类型 动态规划

描述

5月8日,在世界人民的共同关注下,象征着和平、友谊、圣洁的奥运火炬终于来到了世界之巅——珠穆朗玛峰……

登上珠峰可不是所有人都能办得了的,火炬手们为了登山要使用特殊的装备。他有一个带2种气体的气缸:

一个为氧气,一个为氮气。让火炬手需要各种的数量的氧和氮。火炬手有一定数量的气缸。每个气缸都有重量和气体容量。

火炬手为了完成传递需要特定数量的氧和氮。他完成传递所需气缸的总重的最低限度的是多少?

例如:火炬手有5个气缸。每行三个数字为:氧,氮的(升)量和气缸的重量:

3 36 120

10 25 129

5 50 250

1 45 130

4 20 119

如果火炬手需要5升的氧和60升的氮则总重最小为249 (1,2或者4,5号气缸)。

你的任务就是计算火炬手为了完成传递需要的气缸的重量的最低值。

输入格式

输入:

第一行有2整数t,a(1<=t<=21,1<=a<=79)。它们表示氧,氮各自需要的量。

第二行为整数n (1<=n<=1000)表示气缸的个数。

此后的n行,每行包括ti,ai,wi(1<=ti<=21,1<=ai<=79,1<=wi<=800)3整数。

这些各自是:第i个气缸里的氧和氮的容量及汽缸重量。

输出格式

输出:

仅一行包含一个整数,为火炬手完成传递所需的气缸的重量总和的最低值。

样例输入

5 60

5

3 36 120

10 25 129

5 50 250

1 45 130

4 20 119

样例输出

249

*/

#include<climits>

#include<iostream>

using namespace std;

#define MAXINT INT_MAX

#define min(a,b) (a)<(b)?(a):(b)

#define fin cin

#define fout cout

int main (void){

int t,a;

cin>>t>>a;

int dp[22][80];

int n;

cin>>n;

for (int i=0;i<22;i++)

for (int j=0;j<80;j++)

dp[i][j]=MAXINT;

dp[0][0]=0;

for (int i=0;i<n;i++){

int ti,ai,wi;

cin>>ti>>ai>>wi;

for (int k=t;k>=0;k--)

for (int j=a;j>=0;j--)

if (dp[k][j]!=MAXINT){

int x=min(k+ti,t),y=min(j+ai,a);

if (dp[x][y]>dp[k][j]+wi) dp[x][y]=dp[k][j]+wi;

}

}

cout<<dp[t][a];

// while(1);

return 0;

}

#2 B-L-A-C-K@2008-10-27 02:00:00
回复 删除
谁来看下,是不是数据有问题?
查看更多回复
提交回复