Coins

思路

沒分析復雜度寫了個二進制拆分，然后做$01$背包$O(nlog(c)m)>10e7了$，所以還是想辦法優(yōu)化吧。

我們引入一個$need$數(shù)組，$need[j]$表示，在枚舉到第$i$件物品的時候要得到$j$這個狀態(tài)，需要物品$i$的最小個數(shù)。

所以在轉(zhuǎn)移的時候我們只要考慮$need[j - a[i]] < c[i] ? $，如果是符合要求的，并且$dp[j - a[i]]$是在此前可以達到的，

我們就標記$dp[j]$也是可以得到的，然后對$need[j]=need[j?a[i]]+1$，進行數(shù)量上的累加即可。

代碼

/*Author : lifehappy */ #include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10;int dp[N], need[N], v[110], c[110], n, m;int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);while(scanf("%d %d", &n, &m) && (n + m)) {for(int i = 1; i <= n; i++) {scanf("%d", &v[i]);}for(int i = 1; i <= n; i++) {scanf("%d", &c[i]);}memset(dp, 0, sizeof dp);dp[0] = 1;for(int i = 1; i <= n; i++) {memset(need, 0, sizeof need);for(int j = v[i]; j <= m; j++) {if(!dp[j] && need[j - v[i]] < c[i] && dp[j - v[i]]) {dp[j] = 1;need[j] = need[j - v[i]] + 1;}}}int ans = 0;for(int i = 1; i <= m; i++) {ans += dp[i];}printf("%d\n", ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的POJ1742 Coins（DP）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。