哪位好心人帮我看下我的代码有什么改进的地方可以使它不超时啊，谢谢了。。。

#include<stdio.h>

//xxxlxr 1742 Memory Limit Exceed     G++ 0.82K 2005-08-29 15:22:05.0
//xxxlxr 1742 Time Limit Exceed     G++ 0.82K 2005-08-29
//xxxlxr 1742 Runtime Error     G++ 0.83K 2005-08-29 15:28:19.0
//xxxlxr 1742 Time Limit Exceed     C++ 1.04K 2005-08-29 15:43:17.0

const int max1=101;
const int max2=100001;

int n,m;
long a[max1], c[max1];
int f[2][max2];
int fg[max2];
int tm;

void dp()
{
    int t=0;
    int i, j, k;
    for(j=0; j<=m; j++)
     f[0][j]=f[1][j]=fg[j]=0;
    tm=0;
    for(i=0;  i*a[1]<=m && i<=c[1]; i++) f[1][i*a[1]]=1;
    
    for(i=2; i<=n && tm<m+1; i++)
    {
       t=0;
       for(j=0; j<=m; j++)
       {
         int tt=0;
         for(k=0; j>=k*a[i] &&  tt==0 && k<=c[i]; k++) tt+=f[(i-1)%2][j-k*a[i]];

         if(tt>0)
         {
          f[i%2][j]=1; t++;
          if(fg[j]==0)
          {
            fg[j]=1;
            tm++;
          }
         }
         else f[i%2][j]=0;
       }
       if(t==m+1) break;
    }
    
    //for(i=1; i<=m; i++) t+=f[n%2][i];
    //if(tm==m+1) return m;
    //return t-1;
    
}

main()
{
    int i;
    while(scanf("%d %d", &n, &m)==2 && (n || m))
    {
        for(i=1; i<=n; i++)
         scanf("%ld", &a[i]);
        for(i=1; i<=n; i++)
         scanf("%ld", &c[i]);

        dp();
        printf("%d\n", tm-1);
         
    }

}

• 我的程序，2187MS...汗~~~希望能有牛人贴个好的上来 (837) Spacesheep 2005-08-29 23:11:42