题目:采药
状态: Unaccepted
测评机： Xeost[5]
得分： 0分
提交日期： 2010-7-1 22:40:00
有效耗时： 该状态没有记录
测试结果1: 选手程序运行超过时限
测试结果2: 选手程序运行超过时限
测试结果3: 选手程序运行超过时限
测试结果4: 选手程序运行超过时限
测试结果5: 选手程序运行超过时限
测试结果6: 选手程序运行超过时限
测试结果7: 选手程序运行超过时限
测试结果8: 选手程序运行超过时限
测试结果9: 选手程序运行超过时限
测试结果10: 选手程序运行超过时限
提交代码：
#include<stdio.h>
#include<stdlib.h>
main()
{
int times,values,limit,n,temp;
int i,j,max=0,*time,*value;
scanf("%d%d",×,&n);
time=(int*)malloc(n+n);
value=(int*)malloc(n+n);
for(i=0;i<n;i++)
{
scanf("%d%d",&time[i],&value[i]);
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(time[i]<time[j])
{
temp=time[i];
time[i]=time[j];
time[j]=temp;
temp=value[i];
value[i]=value[j];
value[j]=temp;
}
}
}
for(i=0;i<n;i++)
{
limit=0;values=0;
for(j=i;j<n;j++)
{
limit+=time[j];
if(limit>times)
{
limit-=time[j];
continue;
}
values+=value[j];
}
if(values>max)
max=values;
}
printf("%d\n",max);
getch();
}
在帮帮我讲讲啊~~~
这是一道DP啊，这样暴力肯定是会错的……
建议看一下背包问题。
以及getch();这个还是少用，你期待的“程序结束”后仍然会期待输入一个东西来使程序结束。会造成超时问题。
如果以后需要比赛的话，建议还是不要用这个函数。