某种货币，有$N$种面额。 问：在不可找零的情况下，可以支付不超过$13000$元的多少种金额。
第一行一个数$N$ 第二行$N$个数，表示$N$种面额。
一个整数，意义如题所述。
3 3 5 7
12997
$N<=3500$ $总金额<=13000$ 【耗时限制】1000ms 【内存限制】256MB
#include<bits/stdc++.h> using namespace std; int x[3509],n,i,j,k,c=0; bool f[3509][13009]; int main() { cin>>n; for(i=1;i<=n;i++){ cin>>x[i]; f[i][0]=1; } for(k=1;k<=13000/x[1];k++)f[1][x[1]*k]=1; for(i=2;i<=n;i++) for(j=1;j<=13000;j++) for(k=0;k<=j/x[i];k++) if(f[i-1][j-x[i]*k])f[i][j]=1; for(j=1;j<=13000;j++)c+=f[n][j]; cout<<c; }
算一算空间可会超
o
算一算空间可会超
o