| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Multiple && Complete Pack[不转01; 可以不排序]/** * POJ: 3260 The Fewest Coins * * DP: Multiple/Complete Pack * * !!! TLE !!! */ /** ***/ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <limits.h> /** ***/ #define N 100 #define T 10000 #define SP T + 10 #define FJ SP #define SUBMIT 1 /** ***/ #define min(a, b) ( (a) < (b) ? (a) : (b) ) #define max(a, b) ( (a) > (b) ? (a) : (b) ) /** ***/ int knd; // kinds of coins(N); int cst; // the total cost(T); int fj[FJ + 1]; // fj[i]: FJ付款i所用的最小coins int sp[SP + 1]; // sp[j]: SP找零j所用的最小coins typedef struct { int val; int cnt; } coin_t; coin_t con[N + 1]; /** ***/ int compar(const void *p1, const void *p2) { /* descending order */ return ((coin_t *)p2)->val - ((coin_t *)p1)->val; } /** ***/ int main(int argc, char **argv) { #ifndef SUBMIT freopen("input/3260", "r", stdin); #endif int ans = INT_MAX; int mny = 0; // the maximum coins FJ can pay while (2 == scanf("%d%d", &knd, &cst)) { /* init */ ans = INT_MAX; memset(fj, 0, sizeof(fj)); memset(sp, 0, sizeof(sp)); /* input */ for (int i = 1; i <= knd; ++i) { scanf("%d", &con[i].val); } for (int i = 1; i <= knd; ++i) { scanf("%d", &con[i].cnt); } /* sort */ qsort(con + 1, knd, sizeof(coin_t), compar); /* dp -- fj */ for (int i = 1; i <= knd; ++i) { if (!con[i].cnt) { // cnt == 0 时:跳过 continue; } for (int j = mny, nxt; j >= 0; --j) { if (!fj[j] && j) {// fj[j] == j 时的最小值 continue; // fj[0] == 0; } for (int k = 1; k <= con[i].cnt; ++k) { nxt = j + k * con[i].val; if (nxt > T) { break; } if (!fj[nxt]) { fj[nxt] = fj[j] + k; } else { fj[nxt] = min(fj[nxt], fj[j] + k); } mny = max(mny, nxt); } } } /* little optimizations */ if (mny < cst) { printf("-1\n"); continue; } /* dp -- sp */ for (int i = 1; i <= knd; ++i) { for (int j = 1, nxt; j <= mny - cst; ++j) { for (int k = 1; ; ++k) { nxt = k * con[i].val; if (nxt > j) { break; } // 求的是__j可以达到时候__的最小值 if (!sp[j - nxt] && (j ^ nxt)) { continue; } if (!sp[j]) { sp[j] = sp[j - nxt] + k; } else { sp[j] = min(sp[j], sp[j - nxt] + k); } } } } /* resolve */ if (fj[cst]) { ans = min(ans, fj[cst]); } for (int i = cst + 1; i <= mny; ++i) { if (fj[i] && sp[i - cst]) { ans = min(ans, fj[i] + sp[i - cst]); } } /* output */ ans == INT_MAX ? printf("-1\n") : printf("%d\n", ans); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator