0154-Sum of Cards
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0154
個数制限付きナップサック問題かなあと思ってメモ化探索で実装。
がメモ化しなくても時間内に間に合う。
実装(C++)
#include <cstdio> #include <cstring> struct carddata{ int no; int count; }; carddata card[7]; int DP[8][1001]; int m,n,g; int slove(int u,int sum){ int res=0; if(sum==0){ res=1; } else if(sum<0||u>=m){ return 0; } else { if(DP[u][sum]>=0)return DP[u][sum]; for(int i=0;i<=card[u].count;i++){ res+=slove(u+1,sum-i*card[u].no); } } return DP[u][sum]=res; } int main() { int a,b; while(1){ m=0;scanf("%d",&m); if(m==0) break; for(int i=0;i<m;i++){ scanf("%d%d",&a,&b); card[i].no=a; card[i].count=b; } memset(DP,-1,sizeof(DP)); scanf("%d",&g); for(int i=0;i<g;i++){ scanf("%d",&n); printf("%d\n",slove(0,n)); } } return 0; }