(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.
用装箱问题的解法去解(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;
}