jzoj作业【DP】

作业【DP】"/>

jzoj作业【DP】

>Description
光光一共有的时间是 k 小时，老师们一共给光光布置了 n份作业，第 i 份作业需要的时间是 ti 小时。对于一件作业，只有 2 种情况：完成或者不完成（快要完成也算不完成）。
如果没完成，就要受到 pi 个单位的批评。多次这样之后，光光想要知道他至少会受到多少个单位的批评。

>Input
输入文件的第一行只有一个数字 k。
第二行只有一个数字 n。
接下来 n 行，每行两个数字，分别是 ti 和 pi，两个数字之间用一个空格分开。

>Output
输出文件仅包含一行，是一个数字，代表了光光最少受到的批评。

>Sample Input
5
3
2 6
1 3
4 7

>Sample Output
6

【数据范围】
100%的数据中， k<=100000， ti<=10000， pi<=10000；
30%的数据中， n<=20；
100%的数据中， n<=500。

>解题思路
01背包模板。

>代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct ooo
{int t,p;
}a[505];
int k,n,f[100005],sum;
int main()
{
//	freopen("homework.in","r",stdin);
//	freopen("homework.out","w",stdout);scanf("%d%d",&k,&n);for(int i=1;i<=n;i++)scanf("%d%d",&a[i].t,&a[i].p),sum+=a[i].p;for(int i=1;i<=n;i++)for(int j=k;j>=a[i].t;j--)f[j]=max(f[j],f[j-a[i].t]+a[i].p);printf("%d",sum-f[k]);return 0;
}