#include

#include

using namespace std;

long nway[10001];

void Count() {

int i, j, c;

int Coin[] = {1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728, 2197, 2744, 3375, 4096, 4913, 5832, 6859, 8000, 9261};

reverse (Coin, Coin + 21);

nway[0] = 1;

for(i = 0; i < 21; i++) {
c = Coin[i];
for(j = c; j<=10000; j++) {
nway[j] += nway[j-c];
}
}
}
int main() {
long n;
Count();
while(scanf("%ld",&n) != EOF) { // n must be smaller than 1001
printf("%ld\n",nway[n] );
}
return 0;
}
[/sourcecode]

Advertisements

NWAY[]里存的是怎么 ？这个递推式是怎么推出来的？

@发给

suppose, nway [5] = 7

that means, you can make coin 5, in 7 different ways

for example, u have only coins 1, 2, 3

so, in how may ways u can make 5 ?

nway [5] = nway [5-1] + nway [5-2] + nway [5-3]

because,

nway [5-1] + coin 1 = 5

nway [5-2] + coin 2 = 5

nway [5-3] + coin 3 = 5

main prob is limit when it about 10000 then what to do ??

@nayem,

the complexity of the problem is n * m

n = number of coins

m = limits of the coins

so its possible to solve the problem using above method, even when the limit is about 10000

i don’t able to calculate

440022018293 for 9999

because i don’t know how to work for big input !!!!

unsigned long is not applicable there.

then what i need to do??

please give me some hints…

@nayem

Data type: long long (gcc) or __int64 (vc)

Range: –9,223,372,036,854,775,808 to 9,223,372,036,854,775,807

Data type: unsigned long long (gcc) or unsigned __int64 (vc)

Range: 0 to 18,446,744,073,709,551,615

any of these is more than enough to store values

anytime u can use double. though it’s useful to know how to deal with big integer. for now, u can use long long data type in gcc compiler.