#include <stdio.h>
#include <string.h>

int f[2][4510];

int main () {
    int n , m , a , b , i , j , k , rs ;
    while ( scanf ( "%d%d" , &n , &m ) != EOF ) {
        a = 1 ; 
        b = 0 ;
        memset ( f , 0 , sizeof ( f ) ) ;
        for ( i = 0 ; i <= m ; i ++ ) f [1][i] = 1 ;
        for ( k = 2 ; k <= n ; k ++ ) {
            for( i = 0 ; i <= m ; i ++) {
                f[b][i] += f[a][i] ;
                f[b][i] %= 1000000007 ;
                if ( i >= k ) {
                f[b][i] += f[b][i-k] ;
                f[b][i] %= 1000000007 ;
                }                
            }
            memset ( f[a] , 0 , sizeof ( f[a] ) ) ;
            a = 1-a ;
            b = 1-b ;
        }
        printf ("%d\n" , f[a][m] ) ;
    }
    return 0;
}
        

• Re:滚存＋0(m*n)的时间复杂度也TLE疯了，谁教教怎么个优化法！！！！！！ (875) busycai 2006-09-30 17:03:54
  • 你的这个滚动数组用法只能节约内存，时间上反而浪费了，因为每次循环你都要memset (7) asdqwe 2006-09-30 17:18:26