题目描述 Description
Txx是一个成绩很差的人，考试便成了他的噩梦。于是他常在考试时睡觉以打发时间。今天他又要面临一次考试，为了保证有充足的睡眠，他决定只做k分钟题目。这次测试有n道题，第i题的得分是pi分，需要耗费ti分钟解决（将要完成也得不到分）。
请你算出他最少扣多少分（总分是所有题目分值的总和）。
输入描述 Input
Description
Description
第一行k
第二行n
第三行到第n+2行每行两个数：ti和pi
输出描述 Output
Description
Description
Txx最少的扣分
样例输入 Sample
Input
Input
5
3
2 6
1 3
4 7
样例输出 Sample
Output
Output
6
数据范围及提示 Data Size &
Hint
Hint
100%的数据中，k<=100000，ti<=10000，pi<=10000；
30%的数据中，n<=20；
100%的数据中，n<=500
分类标签 Tags 点此展开
代码：
#include
#include
using namespace
std;
std;
const int
INFtim=100001;
INFtim=100001;
const int
INFn=501;
INFn=501;
int
f[INFtim],tim[INFn],fs[INFn];
f[INFtim],tim[INFn],fs[INFn];
int k,n;
long long
sumfs=0;
sumfs=0;
int main()
{
scanf("%d%d",&k,&n);//k sumtim,n ti sum
for(int
i=1;i<=n;++i)
i=1;i<=n;++i)
{
scanf("%d%d",&tim[i],&fs[i]);
sumfs+=fs[i];
}
for(int
i=1;i<=n;++i)
i=1;i<=n;++i)
for(int j=k;j>=1;--j)
if(j-tim[i]>=0)
f[j]=max(f[j],f[j-tim[i]]+fs[i]);
f[j]=max(f[j],f[j-tim[i]]+fs[i]);
printf("%d\n",sumfs-f[k]);
return 0;
}