0154:Sum of Cards
動的計画法で解いた。
dp[ i ][ j ]:=i番目までのカードでj円を作れるパターンの数
#include<iostream> using namespace std; int main(void){ int m,a[8],b[8],g,n,dp[8][1001]; while(cin >> m,m){ for(int i=0;i<8;i++){ for(int j=0;j<1001;j++){ dp[i][j]=0; } } for(int i=0;i<m;i++) cin >> a[i] >> b[i]; for(int j=0;j<=b[0];j++){ dp[0][a[0]*j]++; } for(int i=0;i<m-1;i++){ for(int j=0;j<1001;j++){ for(int k=0;k<=b[i+1];k++){ if(j+(a[i+1]*k)<1001) dp[i+1][j+(a[i+1]*k)]+=dp[i][j]; } } } cin >> g; while(g--){ cin >> n; cout << dp[m-1][n] << endl; } } return 0; }