围观下

#include<stdio.h>
#include<stdlib.h>
int n,inf[30001][3];
void in()
{
     int i;
     scanf("%d",&n);
     for(i=1;i<=n;i++)
       scanf("%d%d%d",&inf[i][0],&inf[i][1],&inf[i][2]);
}
void exc(int i,int j,int k)
{
     int t;
     t=inf[i][k];
     inf[i][k]=inf[j][k];
     inf[j][k]=t;
}
void qusort(int hand,int end)
{
     int i=hand,j=end;
     if(i<j)
       {while(i<j)
          {while(i<j && inf[i][1]<inf[j][1])
             j--;
           if(i<j)
             {exc(i,j,0);
               exc(i,j,1);
               exc(i,j,2);
               i++;
             }
           while(i<j && inf[i][1]<inf[j][1])
             i++;
           if(i<j)
             {exc(i,j,0);
               exc(i,j,1);
               exc(i,j,2);
               j--;
             }
          }
        qusort(hand,i-1);
        qusort(i+1,end);
       }
}            
long int Max()   
{
    int i,k;
    long int m[30001],max;
    m[1]=inf[1][2];
max=m[1];
    for(i=2;i<=n;i++)
      {m[i]=inf[i][2];
   for(k=1;k<i;k++)
         {if(inf[i][0]>=inf[k][1])
            {if(m[i]<m[k]+inf[i][2])
               m[i]=m[k]+inf[i][2];
    }
    else break; 
         }
       if(m[i]>max)
         max=m[i];
      }
    return max;
}        
void out(long int pr)
{
     printf("%ld\n",pr);
}
int main()
{
    long int max;
    in();
    qusort(1,n);
    max=Max();
    out(max);
    system("pause");
    return 0;
}

看着有点麻烦

这个是典型的0-1背包问题，你可以看一本书叫做算法分析与设计，上面有相关算法思想，结合C语言编程应该不算太难。

//#include "MaxIncome.h"

#include <stdio.h>
#include <stdlib.h>


/*
    加工过程
*/
struct item
{
    int start ;
    int end ;
    int cost ;
    struct item *next;
};

void print(struct item * arg) ;

int sum_cost(struct item * arg);
struct item*  getValid(struct item * arg ) ; //得到工作链表
struct item*  getValidItem(struct item * arg, int end) ;
struct item* getStartItem(struct item * arg) ;

int main()
{

    struct item *first = NULL;
    struct item *next = NULL , * tmp = NULL;
    first = (struct item *) malloc(sizeof(struct item)) ;
    first->start = 1 ;
    first->end =3 ;
    first->cost= 10 ;
    tmp = (struct item*) malloc(sizeof(struct item)) ;
    tmp->start = 4 ;
    tmp->end =6 ;
    tmp->cost= 20 ;
   
    next = first ;
    next->next = tmp ;

    next = next->next ;

    tmp = (struct item*) malloc(sizeof(struct item)) ;
    tmp->start = 2 ;
    tmp->end =5 ;
    tmp->cost= 25 ;
    tmp->next = NULL ;
    next->next = tmp ;


    next = next->next ;

    tmp = (struct item*) malloc(sizeof(struct item)) ;
    tmp->start = 7 ;
    tmp->end =9 ;
    tmp->cost= 25 ;
    tmp->next = NULL ;
    next->next = tmp ;

    print(first) ;

    tmp = getValid(first) ;//getStartItem(first) ;

    printf("Max cost: %d\n", sum_cost(tmp) );

    print(tmp) ;
    

    return 0 ;
}

int sum_cost(struct item * arg)
{
    if (arg != NULL)
    {
        struct item * tmp  = arg ;
        int sum = 0 ;
        while (tmp != NULL)
        {
            sum += tmp->cost ;
            tmp = tmp->next ;
        }
        return sum ;
    }
    return 0 ;
}
struct item*  getValid(struct item * arg )
{
                
    struct item * first = NULL, *tmp = NULL , *next = NULL  ;
    first = getStartItem(arg) ;
    printf("first Item --->>> : start=%d, end=%d, cost=%d .\n", first->start, first->end, first->cost) ;
    tmp = arg ;
    next = first ;
    while (next != NULL  && tmp != NULL)
    {
        tmp = getValidItem(tmp, next->end) ;

        next->next = getStartItem(tmp) ;
        next = next->next ;
    }

    return first ;
}

/*
*获得当前结束时间后，可以继续工作的事项链表
*/
struct item*  getValidItem(struct item * arg, int end)
{
    struct item  *first= NULL ;//getStartItem(arg) ;
    struct item  * tmp = arg, *curr = NULL , *tmp1 = NULL;

    while (tmp != NULL)
    {
        if (tmp->start > end)
        {
            tmp1 = (struct item * ) malloc(sizeof(struct item)) ;
            tmp1->start = tmp->start ;
            tmp1->end = tmp->end ;
            tmp1->cost = tmp->cost ;
            tmp1->next = NULL ;
       
            if (first == NULL)
            {
                first = tmp1 ;
                curr=first ;
            }
            else
            {
                curr->next = tmp1 ;
                curr= curr->next ;
            }
        }
        tmp = tmp->next ;
    }

    return first ;

}



/*
*获得开始工作的Item
*/
struct item*  getStartItem(struct item * arg)
{
    struct item * validItem = NULL, *tmp = NULL ;
  
    if (arg != NULL)
    {
        tmp = arg;
        while (tmp != NULL)
        {
           if (validItem == NULL || validItem->start > tmp->start )
           {
               validItem = (struct item *) malloc(sizeof(struct item)) ;
               validItem->start = tmp->start;
               validItem->end = tmp->end ;
               validItem->cost = tmp->cost ;
               validItem->next = NULL ;
           }
           tmp = tmp->next ;
       
        }
    }
   
    return validItem ;
}

/*
*打印工作链表数据   
*/
void print(struct item * arg)
{
    printf("--------------------------------\n") ;
    if (arg != NULL)
    {
        struct item *tmp  = arg ;
        while (arg != NULL)
        {
            printf("start=%d, end=%d, cost=%d .\n", arg->start, arg->end, arg->cost) ;
            arg = arg->next ;
        }
    }else{
        printf("argument is NULL.\n") ;
    }

    printf("--------------------------------\n") ;
}

终于自己练着根据别人的描述 ，写出一个程序啦


--------------------------------
start=1, end=3, cost=10 .
start=4, end=6, cost=20 .
start=2, end=5, cost=25 .
start=7, end=9, cost=25 .
--------------------------------
first Item --->>> : start=1, end=3, cost=10 .
Max cost: 55
--------------------------------
start=1, end=3, cost=10 .
start=4, end=6, cost=20 .
start=7, end=9, cost=25 .
--------------------------------
Press any key to continue

很显然，可用搜索算法，可惜不太会用

不好意思，出差了几天。

看了看大家的代码，其中赵疯子的最靠谱，但有疑问，“while(num++<=t)”，这算怎么回事？

wsws23、笑傲的算是一种贪心策略，在一些情况可以得到最优解，但更多时候得到的算是近似解。

lwb603569640代码中inf的定义和使用存在溢出，算法本身也不能完成题目要求，建议在分析时要细心论证一下。

caidumin，呵呵，我没看到合理的算法，而且再强调一次，释放动态申请的空间。

再说说接口吧，所有提交的代码都没有按照题目要求的输入输出格式写。赵疯子的是最贴近的，但外围那个while循环我实在理解不了。其他人则都加了多余的提示信息。

我们的程序并不一定都是与人互动的，事实上更多时候程序是在与另一个程序、操作系统进行互动通信，与人的互动只存在于人机界面。ACM即是如此，执行你程序的是另一个程序，它看不懂你的提示信息，在裁判程序看来这些提示信息都是错误的输入数据。

最后一个所有人都忽略了的问题，那就是数据的范围。这个题目可能出现的最大数值是30000 * 100000，这个值超出了int型的存储范围，但大部分人用的是int型变量。有人用了long int型变量，我想可能他意识到了int型的范围不够，但目前大多数32位编译器中long int也是32位的，和int没有区别。

失之毫厘，谬以千里。正确的做法是使用无符号32位整型或64位整型。

批评就到这里吧，呵呵，初衷并不是想打击各位，是想各位能更精益求精，请继续努力，加油！

呵呵，严格说来各位只能拿到鼓励奖了。但为鼓励大家多参与，我决定更改奖励规则（放心，只往多改，不往少改）

决定奖励

赵疯子：50专家分

wsws23、笑傲：各20专家分

lwb603569640、caidumin：各5专家分

一会儿请各位到我的奖励贴中报到接分。

最后送上我的代码与大家交流一点编码心得。

关于这个题目大家的理解上有一处歧义，就是开始时间与结束时间相同的问题。到底是单个数据允许相同还是一个数据的开始时间允许与另一个数据的结束时间相同？这两种方式是不能共存的。

由于题目中没有明确描述，也没有实际的OJ可以试验，所以就不在这个问题上纠结了。我的代码是按单个数据允许相同来写的，即认为数据中的时间是一个单位时间长度，而不是一个时间刻度。

#include<stdio.h>
#include<stdlib.h>

int cmp(const void * a, const void * b)
{
    return ((int *)a)[1] - ((int *)b)[1];
}

int main()
{
    long long f[100001], t;
    int a[30000][3], n, from, to, i, j;
    for(; scanf("%d", &n) != EOF; printf("%d\n", f[to]))
    {
        for(from = to = i = 0; i < n; i++)
        {
            scanf("%d%d%d", &a[i][0], &a[i][1], &a[i][2]);
            if(from > a[i][0]) from = a[i][0];
            if(to < a[i][1]) to = a[i][1];
        }
        qsort(a, n, sizeof(a[0]), cmp);
        for(f[from - 1] = 0, j = 0, i = from; i <= to; i++)
        for(f[i] = f[i - 1]; a[j][1] == i; j++)
            if((t = a[j][2] + f[a[j][0] - 1]) > f[i]) f[i] = t;
    }
    return 0;
}

收到的鲜花

• 曾经的梦想 于 2013-06-10 14:24 送鲜花  5朵  
• 韶志 于 2013-06-16 14:57 送鲜花  10朵   附言：好文章

好厉害。在看程序的过程中会思考每个字符所含的意义。但是感觉自己的差距不是一般的大啊。。。。。。。。有点兴奋，有点沮丧