学步园

那个给钱上限是百度的，原来我是用所有的价值加起来作为上线，结果TLE

背包问题都很简单，不过加上优化就可能难一点了

//f1[i]表示支付i元所需的最小硬币数<br /> //f2[i]表示找i元所需的最小硬币数<br /> //买T元东西所需的最小硬币数为f1[T + i] - f2[i]<br /> //f1[i] = min(f1[i], f1[i - k] + 1)<br /> //f2[i] = min(f2[i], f2[i - k] + 1)<br /> //其中f1[i]多重背包，用二进制拆分求解<br /> //f2[i]为完全背包<br /> //其中：给钱上界为：T+maxValue^2，其中maxValue为最大硬币面值。<br /> //证明：反证法。假设存在一种支付方案，John给的钱超过T+maxValue^2，<br /> //则售货员找零超过maxValue^2，则找的硬币数目超过maxValue个，将其看作一数列，<br /> //求前n项和sum(n)，根据鸽巢原理，至少有两 个对maxValue求模的值相等，<br /> //假设为sum(i)和sum(j),i<j，则i+1...j的硬币面值和为maxValue的倍数，<br /> //同理，John给的钱中也有 一定数量的硬币面值和为maxValue的倍数，<br /> //则这两堆硬币可用数量更少的maxValue面值硬币代替，产生更优方案。<br /> #include <iostream><br /> #include <cmath><br /> #include <cstring><br /> using namespace std;<br /> const int MAXN = 101;<br /> const int MAXT = 10000 + 120 * 120 + 1;<br /> const int INF = 200000000;<br /> int f1[MAXT];<br /> int f2[MAXT];<br /> int v[MAXN];<br /> int c[MAXN];<br /> int main() {<br /> //freopen("1.txt", "r", stdin);<br /> int n, T;<br /> while(cin >> n >> T) {<br /> int maxV = 0;<br /> for(int i = 0; i < n; i++) {<br /> cin >> v[i];<br /> maxV = max(maxV, v[i]);<br /> }<br /> maxV *= maxV;<br /> int maxT = T + maxV;<br /> for(int i = 0; i < n; i++)<br /> cin >> c[i];<br /> for(int i = 0; i <= maxT; i++)<br /> f1[i] = f2[i] = INF;<br /> f1[0] = f2[0] = 0;<br /> //完全背包求解<br /> for(int i = 0; i < n; i++) {<br /> for(int j = v[i]; j < maxV; j++) {<br /> f2[j] = min(f2[j], f2[j - v[i]] + 1);<br /> }<br /> }<br /> //多重背包求解<br /> for(int i = 0; i < n; i++) {<br /> int k = 1;<br /> int sum = 0;<br /> while(sum < c[i]) {<br /> for(int j = maxT; j >= v[i] * k; j--) {<br /> f1[j] = min(f1[j], f1[j - v[i] * k] + k);<br /> }<br /> sum += k;<br /> if(sum + k * 2 > c[i])<br /> k = c[i] - sum;<br /> else<br /> k *= 2;<br /> }<br /> }<br /> int _min = INF;<br /> for(int i = T; i <= maxT; i++) {<br /> _min = min(_min, f1[i] + f2[i - T]);<br /> }<br /> if(_min == INF)<br /> printf("-1/n");<br /> else<br /> printf("%d/n", _min);<br /> }<br /> return 0;<br /> }