跳至正文

NOIp 2006 提高组 2 金明的预算方案

  首先要考虑的是,如果没有主件和附件的话,那题目将会非常的简单,那这就是最简单的01背包了,但是麻烦的是题目有主件和附件。那我们怎么办呢?不做了?开玩笑,既然你走了OI这条路,那就千万别回头!那我能不能用01背包来处理这个题目呢?当然是能的,注意题目中的这句话“每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。”额,这个条件有什么用呢?当然有用啦,那么我就可以转化为01背包了,先只考虑主件,那就可以进行01背包了,然后对每个主件进行记录,每个主件拥有多少个附件,哪些附件,然后再进行动态规划就能解决了。
  我把思路再整理一下,就是说先判断主件是否该买,如果它有一个附件的话,那么再考虑是否要购买这一个附件;如果有两个附件的话,那么就考虑是否购买第一个附件,第二个附件或者两个附件一起买(考虑他们的时候就一定要加上主件!)
  代码如下,提交了两次,问题出在一个符号上:

#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
struct thing{
        int priece, cost;
        struct {
                int priece, cost;
        }sub[2];
        int len;
}buy[60];
int num[60];
int len;
int f[32001];

int main(void)
{
        int m, n;
        int i, j, k;
        int a, b, c;
        struct thing t;
        scanf("%d%d", &m, &n);
        for(i = 0; i < n; i++){
                scanf("%d%d%d", &a, &b, &c);
                if(c == 0){
                        num[len++] = i;
                        buy[i].priece = a
b;
                        buy[i].cost = a;
                }else{
                        t = &buy[c – 1];
                        t->sub[t->len].priece = a * b;
                        t->sub[t->len].cost = a;
                        t->len++;
                }
        }
        for(i = 0; i < len; i++){
                t = &buy[num[i]];
                for(j = m; j >= t->cost; j–){
                        f[j] = max(f[j], f[j – t->cost] + t->priece);
                        for(k = 0; k < t->len; k++){
                                if(j – t->cost – t->sub[k].cost >= 0){
                                        f[j] = max(f[j], f[j – t->cost – t->sub[k].cost] + t->priece + t->sub[k].priece);
                                }
                        }
                        if(t->len == 2 && (j – t->cost – t->sub[0].cost – t->sub[1].cost >= 0)){
                                f[j] = max(f[j], f[j – t->cost – t->sub[0].cost – t->sub[1].cost] + t->priece + t->sub[0].priece + t->sub[1].priece);
                                                //把减法写成了加法,, 
                        }
                }
        }
        printf("%d\n", f[m]);
        return 0;
}

发表评论

您的电子邮箱地址不会被公开。