返回信息流试题来源
NOIP2005 普及组
问题描述
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入格式
第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式
包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
样例输入
70 3
71 100
69 1
1 2
样例输出
3
#include <iostream>
using namespace std;
int a[100][1000];
int f(int T,int M)
{
int w[100],p[100];
for(int i=1;i<=M;i++)
{
cin>>w[i]>>p[i];
}
for(int j=2;j<=M;j++)
for(int i=2;i<=M+2-j;i++)
{
if(w[i-1]>w[i])
{
int transw=w[i];
w[i]=w[i-1];
w[i-1]=transw;
int transp=p[i];
p[i]=p[i-1];
p[i-1]=transp;
}
}
for(int i=1;i<=M;i++)
for(int j=0;j<=T;j++)
a[i][j]=0;
for(int i=1;i<=M;i++)
{
for(int j=1;j<=T;j++)
{
if(w[i]<=j)
{
if(a[i-1][j-w[i]]+p[i]>a[i-1][j])
a[i][j]=a[i-1][j-w[i]]+p[i];
}
else{a[i][j]=a[i-1][j];
}
}
}
return a[M][T];
}
int main()
{
int m,n;
cin>>m>>n;
cout<<f(m,n);
return 0;
}
这是一条镜像帖。来源：北邮人论坛 / cpp / #81780同步于 2014/8/25
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
为什么老是过不去检测啊，求大神指点
xiaoxiaoyaa
2014/8/25镜像同步2 回复
订阅后，新回复会通过你的通知中心匿名送达。