#include <stdio.h>
#include <iostream>
using namespace std;

struct fence{
    int l,p,s;
    bool friend operator < (fence a,fence b)
    {
        return a.s<b.s;
    }
}w[101];

int main()
{
  //  freopen("in.txt","r",stdin);
  //  freopen("out.txt","w",stdout);
    int n,i,j,k,tmp;
    int f[16010],g[16010];
    while(scanf("%d%d",&n,&k)!=EOF){
        for(i=0;i<k;i++) scanf("%d%d%d",&w[i].l,&w[i].p,&w[i].s);
        sort(w,w+k);
        // 初始处理
        for(i=0;i<w[0].s;i++) f[i]=g[i]=0;
        for(;i<=n;i++){
            f[i]=i>w[0].l?w[0].l*w[0].p:i*w[0].p;
            g[i]=0;
        }
//      for(i=0;i<=n;i++) printf("%d ",f[i]);
//      printf("\n"); 
        for(j=1;j<k;j++){    // 处理第二个以上的工人
            for(i=w[j].s;i>=0;i--) g[i]=max(g[i+1]-w[j].p,f[i]); 
            for(i=w[j].s+w[j].l-1;i>=w[j].s;i--){
                if(i>w[j].l) f[i]=g[i-w[j].l]+w[j].p*w[j].l;
                else {
                    tmp=i>w[j].l?w[j].l*w[j].p:i*w[j].p;
                    if(tmp>f[i]) f[i]=tmp;
                }
            }
            tmp=f[w[j].s+w[j].l-1];
            for(i=w[j].s+w[j].l;i<=n;i++) f[i]=tmp;  // 向上更新
//            printf("g\n");
//            for(i=0;i<=n;i++) printf("%d ",g[i]);
//            printf("\nf\n");
//            for(i=0;i<=n;i++) printf("%d ",f[i]);
//            printf("\n");
        }
        printf("%d\n",f[n]);
    }
    return 1;
}

• Re:都按着解题报告写啦...为什么还wa呢??一百个不理解... (1199) gohan 2007-07-30 23:53:45
• 哪里可以弄到解题报告啊，下了个ppt看的我晕乎乎 (1545) Thank_you 2007-11-03 16:56:31