POJ.1742 Coins

Problem:
http://poj.org/problem?id=1742

Idea:
dp[i][j]: max leaving (not used) number of a[i] if j is possible to make from first 1..i elements, if not it is -1.

Source:

 const int MAX_K = 100000;  
 int dp[MAX_K + 1];  
 int n, k;  
 int a[111];  
 int m[111];  
 void solve()  
 {  
      memset(dp, -1, sizeof dp);  
      dp[0] = 0;  
      for (int i = 0; i < n; i++) {  
           for (int j = 0; j <= k; j++) {  
                if (dp[j] >= 0)  
                     dp[j] = m[i];  
                else if (j < a[i] || dp[j - a[i]] <= 0)  
                     dp[j] = -1;  
                else  
                     dp[j] = dp[j - a[i]] - 1;  
           }  
      }  
      int ans = 0;  
      for (int i = 1; i <= k; i++)  
           if (dp[i]>=0) ans++;  
      cout << ans << endl;  
 }  
 int main()  
 {  
      while (true) {  
           cin >> n >> k;  
           if (n + k == 0) break;  
           for (int i = 0; i < n; i++) cin >> a[i];  
           for (int i = 0; i < n; i++) cin >> m[i];  
           solve();  
      }  
      return 0;  
 }