分类： 算法

今天把NOIP 2009的所有题目做了一遍，当做考试来做，结果只做出了这一题，而且还只有90分。。死心了。。
代码如下：

/*要注意:
 * 1.\'A\'-\'Z\'扫描完毕就停止, (不管内容还有没有~!)
 * 2,长度小于26就Failed
 * 3,二者是一一对应的关系
 * 4,输入的字符串是密子, 不是原信息
 */
#include <stdio.h>
**char** map[26], mapp[26];
**char** string[101];
**char** start[101], end[101];

**int** main(**void**)
{
 **int** count = 0;
 **int** i;
 scanf(%s, end); //输入的时候写成了%s\\n,,
 scanf(%s, start);
 scanf(%s, string);
 i = 0;
 **while**(count < 26 && end[i] != \'\\0\'){
 **if**(((map[end[i] - \'A\'] > 0) && (map[end[i] - \'A\'] != start[i])) ||
 ((mapp[start[i] - \'A\'] > 0) && (map[start[i] - \'A\'] != end[i]))){
 //两种数据是一一对应的~! 
 **break**;
 }
 **if**(map[end[i] - \'A\'] == 0){ //忘记给count递增了..
 map[end[i] - \'A\'] = start[i];
 mapp[start[i] - \'A\'] = end[i];
 //两种数据是一一对应的~!
 count++;
 }
 i++; //掉了i++
 //差点提交了, 要把i放在判断的外面才行
 }
 **if**(count != 26){
 printf(Failed\\n);
 **return** 0;
 }
 i = 0; //忘记赋值了
 **while**(string[i] != \'\\0\'){
 putchar(map[string[i] - \'A\']);
 i++; //掉了i++
 }
 putchar(\'\\n\');
 **return** 0;
}

顺便提一下，上面的代码是使用Vim转换的！

欧拉回路，我知道怎么做，但是我不知到为什么可以这么做!，囧囧；就当是背课文把，反正这就是欧拉回路。
如果有节点的度为奇数就从它开始，否则就从最小的开始，然后就是看下面的代码把：

 #include <stdio.h>
#define MAXV 500
#define MAXE 1024
char map[MAXV][MAXV];
int path[MAXE];
int degree[MAXV];
int len;
int max;

void add(int a, int b)
{
 map[a][b]++, degree[a]++;
}

void delete(int a, int b)
{
 map[a][b]--, degree[b]--;
}

int getneighbor(int a)
{
 int i;
 for(i = 0; degree[a] != 0; i++){
 if(map[i][a]){
 return i;
 }
 }
}

void fence(int now)
{
 int i;
 while(degree[now]){
 i = getneighbor(now);
 delete(i, now);
 delete(now, i);
 fence(i);
 }
 path[len++] = now;
}

int main(void)
{
 int i;
 int n, k = 501;
 int a, b;
 freopen(fence.in, r, stdin);
 freopen(fence.out, w, stdout);
 scanf(%d, &n);
 for(i = 0; i < n; i++){
 scanf(%d%d, &a, &b);
 a--, b--;
 add(a, b);
 add(b, a);
 if(max < a){
 max = a;
 }
 if(max < b){
 max = b;
 }
 if(k > a){
 k = a;
 }
 if(k > b){
 k = b;
 }
 }
 for(i = 0; i <= max; i++){
 if(degree[i] & 1){
 k = i;
 break;
 }
 }
 fence(k);
 for(i = len - 1; i >= 0; i--){
 printf(%d\\n, path[i] + 1);
 }
 return 0;
}

刚看到题目，我不知所措，真不知道怎么做（NOIP我真的是太菜了。）。
到网上找到了一个高手的结题报告（几个题目我都是搜到的他的。），原来可以用DP来解大致的思路是这样子的：
比如这里有一个循环（只是假设，可能没有这个数）：123 245 344 123，这就是一个循环数，没错吧？，好，再仔细观察一下，第一项和最后一项的后二位数也是相同的，也就是说后k个数循环的长度是后k-1个数循环长度的倍数。
恩，至于代码的话，等下再发上来

(2010年8月4日18:26:10)，这一题希望能成为我的OI转折题，没什么别的，这题我吃了不少亏，总结了几条教训，如下：
1、拿到题目先仔细分析，是否拥有子问题。
上面这一点不只是DP，各种算法都是大事化小，小事化了，不说用什么出众的数学，但是分析题目的时候，没有别的，要理性，争取能够找到更小的问题，然后逐一攻破。
2、不要为了一些微不足道剪纸而丧失了程序的正确性。
总是认为程序的效率很重要，要多用什么位运算，一些小型剪枝。以后的话尽量不要用这些运算，因为Noip只是要确保在规定时间内完成程序，所以100ms和10ms对于成绩来说都是一样的。
3、暂时就说这么多吧。
当然，程序AC之后还是可以适当的优化一下，体验速度给我带来的快乐！
题目的代码如下，可读性自我感觉4颗星！

#include <stdio.h>
#include <string.h>
#define max(a, b) ((a)>(b)?(a):(b))
#define read(a) read_(&a)
#define output(a) output_(&a)
#define mul(a, b) mul_(&a, &b)
#define mulnum(a, b) mulnum_(&a, b)
#define copy(a, b) memcpy((a), (b), sizeof(numtype) * ((b)->len) + sizeof(int))
#define give(a, b) give_(&a, b)
#define getnum(a, i) (a.num[i])
#define MAX 201
const int used = 10;
typedef char numtype;
typedef struct bignum{
 int len;
 numtype num[MAX];
}bignum;
bignum std, x, num, num1, ans;
int k;

void read_(bignum *a)
{
 char tmp[101];
 int i;
 scanf(%s, tmp);
 a->len = strlen(tmp);
 i = a->len - 1;
 while(i >= 0){
 a->num[i] = tmp[a->len - 1 - i] - \'0\';
 i--;
 }
}

void output_(bignum *a)
{
 int i;
 numtype *num = a->num;
 for(i = a->len - 1; i >= 0; i--){
 printf(%d, num[i]);
 }
 printf(\\n);
}

void give_(bignum *a, int n)
{
 int i;
 for(i = 0; n != 0; i++){
 a->num[i] = n % used;
 n /= used;
 }
 a->len = i;
}

void mul_(bignum *a, bignum *b)
{
 static bignum tmp;
 int len = a->len + b->len - 1;
 int i, j;
 numtype re;
 memset(&tmp, 0, sizeof(bignum));
 /* 上面这段代码我错了一次二次三次.. 我最后才知道所有的问题都是它... */
 for(i = 0; i < a->len; i++){
 re = 0;
 for(j = 0; j < b->len; j++){
 tmp.num[i + j] += a->num[i] * b->num[j] + re;
 //是+=
 re = tmp.num[i + j] / used;
 if(re > 0){
 tmp.num[i + j] %= used;
 }
 }
 if(re > 0){
 tmp.num[i + j] = re;
 len = max(i + j + 1, len);
 }
 }
 if(len > k){
 len = k;
 }
 tmp.len = len;
 copy(a, &tmp);
}

void mulnum_(bignum *a, int n)
{
 int i;
 numtype re = 0;
 /* 忘记初始化 */
 for(i = 0; i < a->len; i++){
 a->num[i] = a->num[i] * n + re;
 re = a->num[i] / used;
 if(re > 0){
 a->num[i] %= used;
 }
 }
 if(re > 0){
 a->num[i] = re;
 a->len++;
 } 
}

int main(void)
{
 int i, j;
 int a, b;
 read(std);
 give(ans, 1);
 copy(&x, &std);
 give(ans, 1);
 scanf(%d, &k);
 for(i = 0; i < k; i++){
 copy(&num, &std);
 give(num1, 1);
 b = getnum(std, i);
 for(j = 1; j <= 10; j++){
 mul(num1, x);
 mul(num, x);
 a = getnum(num, i);
 if(a == b){
 copy(&x, &num1);
/* give(t, j);
 mul(ans, t);*/
 mulnum(ans, j);
 break;
 }
 }
 if(j > 10){
 printf(-1\\n);
 return 0;
 }
 }
 output(ans);
 return 0;
}

这题我不怎么说吧，我在网上搜的，到现在为止为什么能这样我还是没想通，只知道这样能过。
就当是个定理吧，记住就是了，这题我不太想解释，看代码吧：

#include <stdio.h>
#define INT_MAX 200000000
int stone[100];
int map[9190], f[9190];

int com(const void *a, const void *b){ return *(int *)a - *(int *)b; }

int main(void)
{
 int i, j, k;
 int l, s, t, n;
 int p, jmp = 0;
 int ans = 0;

 scanf(%d%d%d%d, &l, &s, &t, &n);
 for(i = 0; i <= 9190; i++){
 f[i] = INT_MAX;
 }
 f[0] = 0;
 for(i = 0; i < n; i++){
 scanf(%d, &stone[i]);
 }
 if(s == t){
 for(i = 0; i < n; i++){
 if(stone[i] % s == 0){
 ans++;
 }
 }
 printf(%d\\n, ans);
 return 0;
 }
 qsort(stone, n, sizeof(int), com);
 k = 0;
 for(i = 0; i < n; i++){
 p = stone[i] - k - 1;
 if(p >= s * t){
 jmp += p - s * t;
 }
 map[stone[i] - jmp] = 1;
 k = stone[i];
 }
 if(l - k > s*t){
 jmp += l - k - s*t;
 }
 l -= jmp;
 for(i = 0; i <= l; i++){
 if(f[i] == INT_MAX){
 continue;
 }
 for(j = s; j <= t; j++){
 if(f[i + j] > f[i] + map[i + j]){
 f[i + j] = f[i] + map[i + j];
 }
 }
 }
 for(i = l, ans = INT_MAX; i <= l + t - 1; i++){
 if(ans > f[i]){
 ans = f[i];
 }
 }
 printf(%d\\n, ans);

 return 0;
}

这题一开始我用的那个O(n^3)的算法，叫什么名字我忘了，肯定是超时了咯，因为图是稀疏图，这样是肯定超时的，后来就看标称，看了好久，真没想到标称竟然如此精妙，里面设计了一个能够以O(1)的速度查找元素的功能，整个程序是执行了至多n次Dijkstra算法，然后我在里面增加了一些优化（几乎和时间无关的优化，因为数据量太大，CPU又太好用了），比如用位运算代替乘除法(乘以或除以2)，在上滤和下滤的过程把递归改成了非递归，防止重复的牛所在的牧场进行计算，让heap_val在上滤和下滤的过程中不修改，反正最大的数据程序还是要0.16s才能完成，不知道算不算快。
不过此代码是我写的可读性最低的代码之一，能读都就读吧。

/*
LANG: C
ID: zqynux2
PROG: butter
*/
#include <stdio.h>
const int INTMAX = 1<<30;

int heap_val[800];
int heap_id[800];
int heap_lookup[800];
int heap_size;
#define left(i) (((i) << 1) + 1)
#define right(i) (((i) << 1) + 2)
#define parent(i) ((i - 1) >> 1) 

void heapdown(int t)
{
 int i, ch;
 int id = heap_id[t];
 for(i = t; left(i) < heap_size; i = ch){
 ch = left(i);
 if(ch + 1 < heap_size && heap_val[heap_id[ch + 1]] <
 heap_val[heap_id[ch]]){
 ch++;
 }
 if(heap_val[id] > heap_val[heap_id[ch]]){
 heap_lookup[heap_id[ch]] = i;
 heap_id[i] = heap_id[ch];
 }else{
 break;
 }
 }
 heap_lookup[id] = i;
 heap_id[i] = id;
}

void heapup(int t)
{
 int i;
 int id = heap_id[t];
 for(i = t; i > 0 && heap_val[id]
 < heap_val[heap_id[parent(i)]]; i = parent(i)){
 heap_lookup[heap_id[parent(i)]] = i;
 heap_id[i] = heap_id[parent(i)];
 }
 heap_lookup[id] = i;
 heap_id[i] = id;
}

int cows[500];
int link[800][800];
int value[800][800];
int count[800];
int used[500];
int fixed[800];
int dist[800][800];
int n, p, c;

int main(void)
{
 int i, j, k;
 int t, s;
 freopen(butter.in, r, stdin);
 freopen(butter.out, w, stdout);
 scanf(%d%d%d, &n, &p, &c);
 for(i = 0; i < n; i++){
 scanf(%d, &cows[i]);
 cows[i]--; //掉了这一行代码 
 }
 {
 int a, b, d;
 for(i = 0; i < c; i++){
 scanf(%d%d%d, &a, &b, &d);
 a--, b--;
 link[a][count[a]] = b;
 link[b][count[b]] = a;
 value[a][count[a]] = value[b][count[b]] = d;
 count[a]++, count[b]++;
 }
 }
 for(i = 0; i < n; i++){
 if(used[i]){
 continue;
 }
 used[i] = 1;
 heap_size = p;
 for(j = 0; j < p; j++){
 heap_id[j] = j;
 heap_val[j] = INTMAX;
 heap_lookup[j] = j;
 }
 heap_val[cows[i]] = 0;
 heapup(cows[i]);
 memset(fixed, 0, sizeof(fixed));
 while(heap_size != 0){
 t = heap_id[0];
 dist[cows[i]][t] = heap_val[t];
 fixed[t] = 1;
 heap_size--;
 heap_lookup[heap_id[heap_size]] = 0;
 heap_id[0] = heap_id[heap_size];
 heapdown(0);
 for(k = 0; k < count[t]; k++){
 s = link[t][k];
 if(!fixed[s] && heap_val[s] > heap_val[t] + value[t][k]){
 heap_val[s] = heap_val[t] + value[t][k];
 heapup(heap_lookup[s]);
 }
 }
 }
 }
 {
 int ans = INTMAX, tmp;
 for(i = 0; i < p; i++){
 tmp = 0;
 for(j = 0; j < n; j++){
 tmp += dist[cows[j]][i];
 }
 if(ans > tmp){
 ans = tmp;
 }
 }
 printf(%d\\n, ans);
 }
 return 0;
}

这是个水题，我直接使用了库函数qsort进行了排序，然后输出前五个就可以了，唯一想要说的就是明天或后天把Glibc中的qsort代码看下，学习一下是怎么对超级巨大的数据量进行快速排序的，一个个交换肯定不是，这些都明天再说吧。

#include <stdio.h>
#include <stdlib.h>
#define MAX 300
struct grade{
 int a, b, c;
 int id;
}totle[MAX];
int compare(const void *a, const void *b)
{
 struct grade i = *(struct grade *)a, j = *(struct grade *)b;
 int sum1 = i.a + i.b + i.c,
 sum2 = j.a + j.b + j.c;
 if(sum1 == sum2){
 if(i.a == j.a){
 return i.id - j.id;
 }
 return j.a - i.a;
 }
 return sum2 - sum1;
}

int main(void)
{
 int i;
 int n;
 scanf(%d, &n);
 for(i = 0; i < n; i++){
 totle[i].id = i + 1;
 scanf(%d%d%d, &totle[i].a, &totle[i].b, &totle[i].c);
 }
 qsort(totle, n, sizeof(struct grade), compare);
 for(i = 0; i < 5; i++){
 printf(%d %d\\n, totle[i].id, totle[i].a + totle[i].b +
 totle[i].c);
 }
 return 0;
}

这题困扰了我好几天，详细看了别人的题解，自己反复琢磨，终于琢磨透了。
把我的思路讲一下，f[i][j] 表示第i位(从右向左数, 如12中的1是第二位)，则很容易得到一个DP：
f[i][j] = f[i – 1][j + 1] + f[i – 1][j + 2] + f[i – 1][j + 3] + …. + f[i – 1][n] (n为极限，放在后面讲。)
不用说，用这个递推公式绝对会超时，所以还需要对公式观察一下：
f[i][j] = f[i – 1][j + 1] + f[i – 1][j + 2] + f[i – 1][j + 3] + …. + f[i – 1][n]
上面用红色标记出来的能够用f[i][j + 1] 表示，怎么来的？呵呵，就是因为
f[i][j] = f[i – 1][j + 1] + f[i – 1][j + 2] + f[i – 1][j + 3] + …. + f[i – 1][n] 所以
f[i][j + 1] = f[i – 1][j + 2] + f[i – 1][j + 3] + …. + f[i – 1][n].所以
f[i][j] = f[i][j + 1] + f[i – 1][j + 1]
这就好求了，但是这里需要从大数向小数递减（即j是从n – 1 递减到 1）
然后，我提供一个小剪枝，第i个数的最大值位(1 << k) – j，比如只有一位数字的时候（题目要求至少两位，但是这里只是说明。）当k=3的时候，第一位能够选择的数字是1-7；当有两位数字且k=3是，第二位就只能是1~6而不是1~7了（自己思考下）

还有一个重要的就是需要高精度！！别人都说int要压4位运算，但是这里我压了9位，原因很简单，压4位数的原因是99999^2 > 2^32，就是说当遇到最坏情况下的乘法时，只能使用4位，5位就会溢出；但是这个题目要清楚一点，高精度只用实现加法！所以可以压9位，再多的话也是会超时的。
代码就在下面提供了吧:

#include <stdio.h>
#define MAX 24
#define USED 1000000000
#define max(a, b) ((a)>(b)?(a):(b))
typedef unsigned bignum[MAX];
bignum count[513][513];
bignum ans;

void add(bignum a, bignum b)
{
 int i, j, t;
 int c = max(a[0], b[0]);
 unsigned to = 0;
 if(a[0] < b[0]){
 a[0] = b[0];
 }
 for(i = 0; i < c; i++){
 t = MAX - 1 - i;
 a[t] += b[t] + to;
 to = a[t] / USED;
 if(to > 0){
 a[t] %= USED;
 }
 }
 if(to != 0){
 a[MAX - 1 - i] = to; //狂晕,,, 这里的to写成了t 
 a[0]++;
 }
}

void output(bignum n)
{
 int i, t;
 for(i = MAX - n[0]; i <= MAX - 1; i++){
 printf(%.*d, (i == MAX - n[0]) ? 0 : 9, n[i]);
 }
}

int main(void)
{
 int i, j;
 int top, limit;
 int k, w, n;
 scanf(%d%d, &k, &w);
 n = w / k;
 top = limit = (1 << k) - 1;
 if(w - n * k > 0){
 top = (1 << (w - n * k)) - 1;
 n++;
 }
 if(limit < n){
 n = limit;
 }
 for(i = 1; i <= limit; i++){
 count[1][i][0] = 1;
 count[1][i][MAX - 1] = 1;
 }
 for(i = 2; i <= n; i++){
 for(j = limit - i + 1; j >= 1; j--){
 add(count[i][j], count[i - 1][j + 1]);
 add(count[i][j], count[i][j + 1]);
 }
 }
 for(i = 2; i < n; i++){
 for(j = 1; j <= limit; j++){
 add(ans, count[i][j]);
 }
 }
 for(j = 1; j <= top; j++){
 add(ans, count[i][j]);
 }
 output(ans);
 return 0;
}

这题二话不说, 用map[i][j]表示坐标为i, j的点是什么颜色的.. 很快就写出来了, 但是内存超过了,, 内存最多16MB.
没办法, 只好另辟思路, 但是在数据压缩方面我又很弱, 就看标程也花了两三天的时间, 今天终于是看懂了..
用rect记录所有矩形的坐标以及相应的颜色.
程序具体的步骤如下:

输入A, B, N. 记录第一个矩形: (0, 0) (A, B), 颜色为1
接着读入其余的矩形, 设当前是第i个
对i之前所有的矩形迭代, 此时迭代到的是第j个.
判断i是否完全包含j, 即: i.x1 >= j.x1 && i.x2 >= j.x2 && i.y1 <= j.y1 && i.y2 >= j.y2..
若全包围的话, 将第j个矩形删除.
如果没包围的话, 就判断i会将j拆分成几个矩形, 并将j删除, 再分别拆分的矩形分别放入rect中.

/*
LANG: C
ID: zqy11001
PROG: rect1
*/
#include <stdio.h>
#include <string.h>
#define MAX 10001
#define getint(i) scanf(%d, &i)
#define loop(i, j, k, l)\\
if(a.i l b.i){\\
 t = a;\\
 t.j = b.k;\\
 tmp[n++] = t;\\
 a.i = b.i;\\
}

struct rect{
 int t;
 int x1, x2, y1, y2;
}rect[MAX];
int rr;
int color[2500];

int func(struct rect a, const struct rect b, struct rect *tmp)
{
 int n;
 struct rect t;
 if(b.x1 >= a.x2 || b.x2 <= a.x1 || b.y1 >= a.y2 || b.y2 <= a.y1){
 return 0;
 }
 if(b.x1 <= a.x1 && b.x2 >= a.x2 && b.y1 <= a.y1 && b.y2 >= a.y2){
 return -1;
 }

 n = 0;
 loop(x1, x2, x1, <=);
 loop(x2, x1, x2, >=);
 loop(y1, y2, y1, <=);
 loop(y2, y1, y2, >=);
 return n;
}

int main(void)
{
 int n, nr, m;
 int a, b, i, j, k;
 struct rect t[4], cur;
 freopen(rect1.in, r, stdin);
 freopen(rect1.out, w, stdout);
 getint(a);
 getint(b);
 getint(n);

 rect[0].x1 = rect[0].y1 = 0;
 rect[0].x2 = a;
 rect[0].y2 = b;
 rect[0].t = 1;

 rr = 1;
 for(i = 1; i <= n; i++){
 scanf(%d%d%d%d%d, &rect[rr].x1, &rect[rr].y1, 
 &rect[rr].x2, &rect[rr].y2, &rect[rr].t);
 cur = rect[rr++];
 nr = rr - 1;
 for(j = 0; j < nr; j++){
 m = func(rect[j], cur, t);
 if(!m){
 continue;
 }
 if(m < 0){
 memmove(rect + j, rect + j + 1,
 sizeof(struct rect) * (rr - j - 1));
 j--;
 rr--;
 nr--;
 continue;
 }
 rect[j] = t[--m];
 while(m--){
 rect[rr++] = t[m];
 }
 }
 }
 memset(color, 0, sizeof(color));
 for(i = 0; i < rr; i++){
 color[rect[i].t - 1] += (rect[i].x2 - rect[i].x1) *
 (rect[i].y2 - rect[i].y1);
 }

 for(i = 0; i < 2500; i++){
 if(color[i]){
 printf(%d %d\\n, i + 1, color[i]);
 }
 }
 return 0;
}

从这一题开始,, 以后题目我就不贴上来了… 自己去看吧..

这一题开始肯本看不懂,, 后来是反反复复看标程看懂了..

首先要理解这么一个式子吧(算是式子吧“)

已经求出了j-1个丑数,, 现在求第j个丑数

对于每一个素数p乘以一个最小的丑数, 能使积大于第j-1个丑数

在这些乘积中寻找最小的一个即位第j个丑数.

用pindex[i]表示对于第i个素数乘以的最小丑数是多少..

/*
LANG: C
ID: zqy11001
PROG: humble
*/
#include 
#include 
#define MAX 100
#define getint(i) scanf(%d, &i)
#define insert(i) hum[count++] = i

long hum[1000001];
int pindex[MAX];
int prime[MAX];
int count;

int main(void)
{
 int k, n;
 int i;
 int min, m;
 freopen(humble.in, r, stdin);
 freopen(humble.out, w, stdout);
 getint(k);
 getint(n);
 for(i = 0; i < k; i++){
 getint(prime[i]);
 }

 insert(1);
 memset(pindex, 0, sizeof(int)*k);
 while(count <= n){
 min = 0x7FFFFFFF;
 for(i = 0; i < k; i++){
 while(prime[i] * hum[pindex[i]] <= hum[count - 1]){
 pindex[i]++;
 }

 if(prime[i] * hum[pindex[i]] < min){
 min = prime[i] * hum[pindex[i]];
 m = i;
 }
 }
 insert(min);
 }

 printf(%d\\n, hum[n]);
 return 0;
}

Score Inflation

The more points students score in our contests, the happier we here at the USACO are. We try to design our contests so that people can score as many points as possible, and would like your assistance.

We have several categories from which problems can be chosen, where a "category" is an unlimited set of contest problems which all require the same amount of time to solve and deserve the same number of points for a correct solution. Your task is write a program which tells the USACO staff how many problems from each category to include in a contest so as to maximize the total number of points in the chosen problems while keeping the total solution time within the length of the contest.

The input includes the length of the contest, M (1 <= M <= 10,000) (don’t worry, you won’t have to compete in the longer contests until training camp) and N, the number of problem categories, where 1 <= N <= 10,000.

Each of the subsequent N lines contains two integers describing a category: the first integer tells the number of points a problem from that category is worth (1 <= points <= 10000); the second tells the number of minutes a problem from that category takes to solve (1 <= minutes <= 10000).

Your program should determine the number of problems we should take from each category to make the highest-scoring contest solvable within the length of the contest. Remember, the number from any category can be any nonnegative integer (0, one, or many). Calculate the maximum number of possible points.

PROGRAM NAME: inflate
INPUT FORMAT
Line 1:  M, N — contest minutes and number of problem classes 
Lines 2-N+1:  Two integers: the points and minutes for each class

SAMPLE INPUT (file inflate.in)
300 4
100 60
250 120
120 100
35 20

OUTPUT FORMAT
A single line with the maximum number of points possible given the constraints.
SAMPLE OUTPUT (file inflate.out)
605


描述
学生在我们USACO的竞赛中的得分越多我们越高兴。

我们试着设计我们的竞赛以便人们能尽可能的多得分,这需要你的帮助。

我们可以从几个种类中选取竞赛的题目,这里的一个"种类"是指一个竞赛题目的集合,解决集合中的题目需要相同多的时间并且能得到相同的分数。你的任务是写一个程序来告诉USACO的职员,应该从每一个种类中选取多少题目,使得解决题目的总耗时在竞赛规定的时间里并且总分最大。输入包括竞赛的时间,M(1 <= M <= 10,000)(不要担心,你要到了训练营中才会有长时间的比赛)和N,"种类"的数目1 <= N <= 10,000。后面的每一行将包括两个整数来描述一个"种类":

第一个整数说明解决这种题目能得的分数(1 <= points <= 10000),第二整数说明解决这种题目所需的时间(1 <= minutes <= 10000)。你的程序应该确定我们应该从每个"种类"中选多少道题目使得能在竞赛的时间中得到最大的分数。

来自任意的"种类"的题目数目可能任何非负数(0或更多)。

计算可能得到的最大分数。

格式
PROGRAM NAME: inflate

INPUT FORMAT：

(file inflate.in)

第 1 行: M, N–竞赛的时间和题目"种类"的数目。

第 2-N+1 行: 两个整数:每个"种类"题目的分数和耗时。

OUTPUT FORMAT：

(file inflate.out)

单独的一行包括那个在给定的限制里可能得到的最大的分数。

SAMPLE INPUT
300 4
100 60
250 120
120 100
35 20
SAMPLE OUTPUT
605


======================== 华丽的分割线 ========================
　　标准的无限背包,, 看<<背包9讲>>

/*
LANG: C
ID: zqy11001
PROG: inflate
*/
#include <stdio.h>
#define getint(i) scanf(%d, &i)
#define max(a, b) ((a)>(b)?(a):(b))

int f[10001];

int main(void)
{
 int n, m;
 int i, j, t;
 int a, b;
 freopen(inflate.in, r, stdin);
 freopen(inflate.out, w, stdout);
 getint(m);
 getint(n);
 for(i = 1; i <= n; i++){
 scanf(%d%d, &a, &b);
 for(j = b; j <= 10000; j++){
 t = f[j - b] + a;
 f[j] = max(f[j], t);
 }
 }
 printf(%d\\n, f[m]);
 return 0;
}